
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>十大经典排序算法 · 夜尽天明的博客</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="biaochenxuying">
        <meta id="referrer" name="referrer" content="never" />
        
    
    <link rel="stylesheet" href="../../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../../gitbook/gitbook-plugin-donate/plugin.css">
                
            
                
                <link rel="stylesheet" href="../../gitbook/gitbook-plugin-tbfed-pagefooter/footer.css">
                
            
                
                <link rel="stylesheet" href="../../gitbook/gitbook-plugin-anchor-navigation-ex/style/plugin.css">
                
            
                
                <link rel="stylesheet" href="../../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
    
        
    
        
    
        
    
        
    
        
    

        
    
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../../gitbook/images/favicon.ico" type="image/x-icon">

    
    
    <link rel="prev" href="js-time-space.html" />
    

    <style>
    @media only screen and (max-width: 640px) {
        .book-header .hidden-mobile {
            display: none;
        }
    }
    </style>
    <script>
        window["gitbook-plugin-github-buttons"] = {"buttons":[{"user":"biaochenxuying","repo":"blog","type":"star","count":true,"size":"small"},{"user":"biaochenxuying","width":"160","type":"follow","count":true,"size":"small"}]};
    </script>

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        
    
        <li class="chapter " data-level="1.1" data-path="../../">
            
                <a href="../../">
            
                    
                    简介
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="../github/follow.html">
            
                <a href="../github/follow.html">
            
                    
                    GitHub 吸星大法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../github/star.html">
            
                <a href="../github/star.html">
            
                    
                    GitHub 挖宝技巧
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" >
            
                <span>
            
                    
                    Vue.js
            
                </span>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.4.1" data-path="../vue/vue-ts.html">
            
                <a href="../vue/vue-ts.html">
            
                    
                    Vue + TS + El 搭建博客及踩坑记
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.5" >
            
                <span>
            
                    
                    JavaScript 数据结构与算法之美
            
                </span>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.5.1" data-path="js-time-space.html">
            
                <a href="js-time-space.html">
            
                    
                    时间和空间复杂度
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="1.5.2" data-path="js-10algo.html">
            
                <a href="js-10algo.html">
            
                    
                    十大经典排序算法
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="../.." >十大经典排序算法</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <div id="anchor-navigation-ex-navbar"><i class="fa fa-navicon"></i><ul><li><span class="title-icon "></span><a href="#&#x5341;&#x5927;&#x7ECF;&#x5178;&#x7B97;&#x6CD5;"><b></b>&#x5341;&#x5927;&#x7ECF;&#x5178;&#x7B97;&#x6CD5;</a></li><ul><li><span class="title-icon "></span><a href="#1-&#x524D;&#x8A00;"><b></b>1. &#x524D;&#x8A00;</a></li><li><span class="title-icon "></span><a href="#2-&#x5982;&#x4F55;&#x5206;&#x6790;&#x4E00;&#x4E2A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;"><b></b>2. &#x5982;&#x4F55;&#x5206;&#x6790;&#x4E00;&#x4E2A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;</a></li><ul><li><span class="title-icon "></span><a href="#21-&#x6267;&#x884C;&#x6548;&#x7387;"><b></b>2.1 &#x6267;&#x884C;&#x6548;&#x7387;</a></li><li><span class="title-icon "></span><a href="#22-&#x5185;&#x5B58;&#x6D88;&#x8017;"><b></b>2.2 &#x5185;&#x5B58;&#x6D88;&#x8017;</a></li><li><span class="title-icon "></span><a href="#23-&#x7A33;&#x5B9A;&#x6027;"><b></b>2.3 &#x7A33;&#x5B9A;&#x6027;</a></li></ul><li><span class="title-icon "></span><a href="#3-&#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;"><b></b>3. &#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;</a></li><ul><li><span class="title-icon "></span><a href="#31-&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#xFF08;bubble-sort&#xFF09;"><b></b>3.1 &#x5192;&#x6CE1;&#x6392;&#x5E8F;&#xFF08;Bubble Sort&#xFF09;</a></li><li><span class="title-icon "></span><a href="#32-&#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF08;insertion-sort&#xFF09;"><b></b>3.2 &#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF08;Insertion Sort&#xFF09;</a></li><li><span class="title-icon "></span><a href="#33-&#x9009;&#x62E9;&#x6392;&#x5E8F;&#xFF08;selection-sort&#xFF09;"><b></b>3.3 &#x9009;&#x62E9;&#x6392;&#x5E8F;&#xFF08;Selection Sort&#xFF09;</a></li><li><span class="title-icon "></span><a href="#34-&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#xFF08;merge-sort&#xFF09;"><b></b>3.4 &#x5F52;&#x5E76;&#x6392;&#x5E8F;&#xFF08;Merge Sort&#xFF09;</a></li><li><span class="title-icon "></span><a href="#35-&#x5FEB;&#x901F;&#x6392;&#x5E8F;-&#xFF08;quick-sort&#xFF09;"><b></b>3.5 &#x5FEB;&#x901F;&#x6392;&#x5E8F; &#xFF08;Quick Sort&#xFF09;</a></li><li><span class="title-icon "></span><a href="#36-&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#xFF08;shell-sort&#xFF09;"><b></b>3.6 &#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#xFF08;Shell Sort&#xFF09;</a></li><li><span class="title-icon "></span><a href="#37-&#x5806;&#x6392;&#x5E8F;&#xFF08;heap-sort&#xFF09;"><b></b>3.7 &#x5806;&#x6392;&#x5E8F;&#xFF08;Heap Sort&#xFF09;</a></li><li><span class="title-icon "></span><a href="#38-&#x6876;&#x6392;&#x5E8F;&#xFF08;bucket-sort&#xFF09;"><b></b>3.8 &#x6876;&#x6392;&#x5E8F;&#xFF08;Bucket Sort&#xFF09;</a></li><li><span class="title-icon "></span><a href="#39-&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#xFF08;counting-sort&#xFF09;"><b></b>3.9 &#x8BA1;&#x6570;&#x6392;&#x5E8F;&#xFF08;Counting Sort&#xFF09;</a></li><li><span class="title-icon "></span><a href="#310-&#x57FA;&#x6570;&#x6392;&#x5E8F;&#xFF08;radix-sort&#xFF09;"><b></b>3.10 &#x57FA;&#x6570;&#x6392;&#x5E8F;&#xFF08;Radix Sort&#xFF09;</a></li></ul><li><span class="title-icon "></span><a href="#4-&#x590D;&#x6742;&#x5EA6;&#x5BF9;&#x6BD4;"><b></b>4. &#x590D;&#x6742;&#x5EA6;&#x5BF9;&#x6BD4;</a></li><li><span class="title-icon "></span><a href="#5-&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177;"><b></b>5. &#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177;</a></li><li><span class="title-icon "></span><a href="#6-&#x7CFB;&#x5217;&#x6587;&#x7AE0;"><b></b>6. &#x7CFB;&#x5217;&#x6587;&#x7AE0;</a></li><li><span class="title-icon "></span><a href="#7-&#x6700;&#x540E;"><b></b>7. &#x6700;&#x540E;</a></li></ul></ul></div><a href="#&#x5341;&#x5927;&#x7ECF;&#x5178;&#x7B97;&#x6CD5;" id="anchorNavigationExGoTop"><i class="fa fa-arrow-up"></i></a><h1 id="&#x5341;&#x5927;&#x7ECF;&#x5178;&#x7B97;&#x6CD5;"><a name="&#x5341;&#x5927;&#x7ECF;&#x5178;&#x7B97;&#x6CD5;" class="anchor-navigation-ex-anchor" href="#&#x5341;&#x5927;&#x7ECF;&#x5178;&#x7B97;&#x6CD5;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x5341;&#x5927;&#x7ECF;&#x5178;&#x7B97;&#x6CD5;</h1>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-9f08a1abed2d7caf.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E;"></p>
<h2 id="1-&#x524D;&#x8A00;"><a name="1-&#x524D;&#x8A00;" class="anchor-navigation-ex-anchor" href="#1-&#x524D;&#x8A00;"><i class="fa fa-link" aria-hidden="true"></i></a>1. &#x524D;&#x8A00;</h2>
<blockquote>
<p>&#x7B97;&#x6CD5;&#x4E3A;&#x738B;&#x3002;</p>
<p>&#x60F3;&#x5B66;&#x597D;&#x524D;&#x7AEF;&#xFF0C;&#x5148;&#x7EC3;&#x597D;&#x5185;&#x529F;&#xFF0C;&#x5185;&#x529F;&#x4E0D;&#x884C;&#xFF0C;&#x5C31;&#x7B97;&#x62DB;&#x5F0F;&#x7EC3;&#x7684;&#x518D;&#x82B1;&#x54E8;&#xFF0C;&#x7EC8;&#x7A76;&#x6210;&#x4E0D;&#x4E86;&#x9AD8;&#x624B;&#xFF1B;&#x53EA;&#x6709;&#x5185;&#x529F;&#x6DF1;&#x539A;&#x8005;&#xFF0C;&#x524D;&#x7AEF;&#x4E4B;&#x8DEF;&#x624D;&#x4F1A;&#x8D70;&#x5F97;&#x66F4;&#x8FDC;&#x3002;</p>
</blockquote>
<p>&#x7B14;&#x8005;&#x5199;&#x7684; <strong>JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E;</strong> &#x7CFB;&#x5217;&#x7528;&#x7684;&#x8BED;&#x8A00;&#x662F; <strong>JavaScript</strong> &#xFF0C;&#x65E8;&#x5728;&#x5165;&#x95E8;&#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x548C;&#x65B9;&#x4FBF;&#x4EE5;&#x540E;&#x590D;&#x4E60;&#x3002;</p>
<p>&#x6587;&#x4E2D;&#x5305;&#x542B;&#x4E86; <code>&#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;</code> &#x7684;&#x601D;&#x60F3;&#x3001;&#x4EE3;&#x7801;&#x5B9E;&#x73B0;&#x3001;&#x4E00;&#x4E9B;&#x4F8B;&#x5B50;&#x3001;&#x590D;&#x6742;&#x5EA6;&#x5206;&#x6790;&#x3001;&#x52A8;&#x753B;&#x3001;&#x8FD8;&#x6709;&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177;&#x3002;</p>
<p>&#x8FD9;&#x5E94;&#x8BE5;&#x662F;&#x76EE;&#x524D;&#x6BD4;&#x8F83;&#x5168;&#x7684; <code>JavaScript &#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;</code> &#x7684;&#x8BB2;&#x89E3;&#x4E86;&#x5427;&#x3002;</p>
<h2 id="2-&#x5982;&#x4F55;&#x5206;&#x6790;&#x4E00;&#x4E2A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;"><a name="2-&#x5982;&#x4F55;&#x5206;&#x6790;&#x4E00;&#x4E2A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;" class="anchor-navigation-ex-anchor" href="#2-&#x5982;&#x4F55;&#x5206;&#x6790;&#x4E00;&#x4E2A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;"><i class="fa fa-link" aria-hidden="true"></i></a>2. &#x5982;&#x4F55;&#x5206;&#x6790;&#x4E00;&#x4E2A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;</h2>
<p>&#x590D;&#x6742;&#x5EA6;&#x5206;&#x6790;&#x662F;&#x6574;&#x4E2A;&#x7B97;&#x6CD5;&#x5B66;&#x4E60;&#x7684;&#x7CBE;&#x9AD3;&#x3002;</p>
<ul>
<li>&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;: &#x4E00;&#x4E2A;&#x7B97;&#x6CD5;&#x6267;&#x884C;&#x6240;&#x8017;&#x8D39;&#x7684;&#x65F6;&#x95F4;&#x3002; </li>
<li>&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;: &#x8FD0;&#x884C;&#x5B8C;&#x4E00;&#x4E2A;&#x7A0B;&#x5E8F;&#x6240;&#x9700;&#x5185;&#x5B58;&#x7684;&#x5927;&#x5C0F;&#x3002;</li>
</ul>
<p>&#x65F6;&#x95F4;&#x548C;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x7684;&#x8BE6;&#x89E3;&#xFF0C;&#x8BF7;&#x770B; <a href="https://juejin.im/post/5cf37b6d6fb9a07eb15d3e88" target="_blank">JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x65F6;&#x95F4;&#x548C;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;</a>&#x3002;</p>
<p>&#x5B66;&#x4E60;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x6211;&#x4EEC;&#x9664;&#x4E86;&#x5B66;&#x4E60;&#x5B83;&#x7684;&#x7B97;&#x6CD5;&#x539F;&#x7406;&#x3001;&#x4EE3;&#x7801;&#x5B9E;&#x73B0;&#x4E4B;&#x5916;&#xFF0C;&#x66F4;&#x91CD;&#x8981;&#x7684;&#x662F;&#x8981;&#x5B66;&#x4F1A;&#x5982;&#x4F55;&#x8BC4;&#x4EF7;&#x3001;&#x5206;&#x6790;&#x4E00;&#x4E2A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
<p>&#x5206;&#x6790;&#x4E00;&#x4E2A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x8981;&#x4ECE; <code>&#x6267;&#x884C;&#x6548;&#x7387;</code>&#x3001;<code>&#x5185;&#x5B58;&#x6D88;&#x8017;</code>&#x3001;<code>&#x7A33;&#x5B9A;&#x6027;</code> &#x4E09;&#x65B9;&#x9762;&#x5165;&#x624B;&#x3002;</p>
<h3 id="21-&#x6267;&#x884C;&#x6548;&#x7387;"><a name="21-&#x6267;&#x884C;&#x6548;&#x7387;" class="anchor-navigation-ex-anchor" href="#21-&#x6267;&#x884C;&#x6548;&#x7387;"><i class="fa fa-link" aria-hidden="true"></i></a>2.1 &#x6267;&#x884C;&#x6548;&#x7387;</h3>
<p><strong>1. &#x6700;&#x597D;&#x60C5;&#x51B5;&#x3001;&#x6700;&#x574F;&#x60C5;&#x51B5;&#x3001;&#x5E73;&#x5747;&#x60C5;&#x51B5;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;</strong></p>
<p>&#x6211;&#x4EEC;&#x5728;&#x5206;&#x6790;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x65F6;&#xFF0C;&#x8981;&#x5206;&#x522B;&#x7ED9;&#x51FA;&#x6700;&#x597D;&#x60C5;&#x51B5;&#x3001;&#x6700;&#x574F;&#x60C5;&#x51B5;&#x3001;&#x5E73;&#x5747;&#x60C5;&#x51B5;&#x4E0B;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x3002;
&#x9664;&#x6B64;&#x4E4B;&#x5916;&#xFF0C;&#x4F60;&#x8FD8;&#x8981;&#x8BF4;&#x51FA;&#x6700;&#x597D;&#x3001;&#x6700;&#x574F;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x5BF9;&#x5E94;&#x7684;&#x8981;&#x6392;&#x5E8F;&#x7684;&#x539F;&#x59CB;&#x6570;&#x636E;&#x662F;&#x4EC0;&#x4E48;&#x6837;&#x7684;&#x3002;</p>
<p><strong>2. &#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x7684;&#x7CFB;&#x6570;&#x3001;&#x5E38;&#x6570; &#x3001;&#x4F4E;&#x9636;</strong></p>
<p>&#x6211;&#x4EEC;&#x77E5;&#x9053;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x53CD;&#x5E94;&#x7684;&#x662F;&#x6570;&#x636E;&#x89C4;&#x6A21; n &#x5F88;&#x5927;&#x7684;&#x65F6;&#x5019;&#x7684;&#x4E00;&#x4E2A;&#x589E;&#x957F;&#x8D8B;&#x52BF;&#xFF0C;&#x6240;&#x4EE5;&#x5B83;&#x8868;&#x793A;&#x7684;&#x65F6;&#x5019;&#x4F1A;&#x5FFD;&#x7565;&#x7CFB;&#x6570;&#x3001;&#x5E38;&#x6570;&#x3001;&#x4F4E;&#x9636;&#x3002;</p>
<p>&#x4F46;&#x662F;&#x5B9E;&#x9645;&#x7684;&#x8F6F;&#x4EF6;&#x5F00;&#x53D1;&#x4E2D;&#xFF0C;&#x6211;&#x4EEC;&#x6392;&#x5E8F;&#x7684;&#x53EF;&#x80FD;&#x662F; 10 &#x4E2A;&#x3001;100 &#x4E2A;&#x3001;1000 &#x4E2A;&#x8FD9;&#x6837;&#x89C4;&#x6A21;&#x5F88;&#x5C0F;&#x7684;&#x6570;&#x636E;&#xFF0C;&#x6240;&#x4EE5;&#xFF0C;&#x5728;&#x5BF9;&#x540C;&#x4E00;&#x9636;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x6027;&#x80FD;&#x5BF9;&#x6BD4;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x6211;&#x4EEC;&#x5C31;&#x8981;&#x628A;&#x7CFB;&#x6570;&#x3001;&#x5E38;&#x6570;&#x3001;&#x4F4E;&#x9636;&#x4E5F;&#x8003;&#x8651;&#x8FDB;&#x6765;&#x3002;</p>
<p><strong>3. &#x6BD4;&#x8F83;&#x6B21;&#x6570;&#x548C;&#x4EA4;&#x6362;&#xFF08;&#x6216;&#x79FB;&#x52A8;&#xFF09;&#x6B21;&#x6570;</strong></p>
<p>&#x8FD9;&#x4E00;&#x8282;&#x548C;&#x4E0B;&#x4E00;&#x8282;&#x8BB2;&#x7684;&#x90FD;&#x662F;&#x57FA;&#x4E8E;&#x6BD4;&#x8F83;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;&#x57FA;&#x4E8E;&#x6BD4;&#x8F83;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x6267;&#x884C;&#x8FC7;&#x7A0B;&#xFF0C;&#x4F1A;&#x6D89;&#x53CA;&#x4E24;&#x79CD;&#x64CD;&#x4F5C;&#xFF0C;&#x4E00;&#x79CD;&#x662F;&#x5143;&#x7D20;&#x6BD4;&#x8F83;&#x5927;&#x5C0F;&#xFF0C;&#x53E6;&#x4E00;&#x79CD;&#x662F;&#x5143;&#x7D20;&#x4EA4;&#x6362;&#x6216;&#x79FB;&#x52A8;&#x3002;</p>
<p>&#x6240;&#x4EE5;&#xFF0C;&#x5982;&#x679C;&#x6211;&#x4EEC;&#x5728;&#x5206;&#x6790;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x6267;&#x884C;&#x6548;&#x7387;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x5E94;&#x8BE5;&#x628A;&#x6BD4;&#x8F83;&#x6B21;&#x6570;&#x548C;&#x4EA4;&#x6362;&#xFF08;&#x6216;&#x79FB;&#x52A8;&#xFF09;&#x6B21;&#x6570;&#x4E5F;&#x8003;&#x8651;&#x8FDB;&#x53BB;&#x3002;</p>
<h3 id="22-&#x5185;&#x5B58;&#x6D88;&#x8017;"><a name="22-&#x5185;&#x5B58;&#x6D88;&#x8017;" class="anchor-navigation-ex-anchor" href="#22-&#x5185;&#x5B58;&#x6D88;&#x8017;"><i class="fa fa-link" aria-hidden="true"></i></a>2.2 &#x5185;&#x5B58;&#x6D88;&#x8017;</h3>
<p>&#x4E5F;&#x5C31;&#x662F;&#x770B;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x3002;</p>
<p>&#x8FD8;&#x9700;&#x8981;&#x77E5;&#x9053;&#x5982;&#x4E0B;&#x672F;&#x8BED;&#xFF1A;</p>
<ul>
<li><strong>&#x5185;&#x6392;&#x5E8F;</strong>&#xFF1A;&#x6240;&#x6709;&#x6392;&#x5E8F;&#x64CD;&#x4F5C;&#x90FD;&#x5728;&#x5185;&#x5B58;&#x4E2D;&#x5B8C;&#x6210;&#xFF1B; </li>
<li><strong>&#x5916;&#x6392;&#x5E8F;</strong>&#xFF1A;&#x7531;&#x4E8E;&#x6570;&#x636E;&#x592A;&#x5927;&#xFF0C;&#x56E0;&#x6B64;&#x628A;&#x6570;&#x636E;&#x653E;&#x5728;&#x78C1;&#x76D8;&#x4E2D;&#xFF0C;&#x800C;&#x6392;&#x5E8F;&#x901A;&#x8FC7;&#x78C1;&#x76D8;&#x548C;&#x5185;&#x5B58;&#x7684;&#x6570;&#x636E;&#x4F20;&#x8F93;&#x624D;&#x80FD;&#x8FDB;&#x884C;&#xFF1B;</li>
<li><strong>&#x539F;&#x5730;&#x6392;&#x5E8F;</strong>&#xFF1A;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x5C31;&#x662F;&#x7279;&#x6307;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; O(1) &#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
</ul>
<h3 id="23-&#x7A33;&#x5B9A;&#x6027;"><a name="23-&#x7A33;&#x5B9A;&#x6027;" class="anchor-navigation-ex-anchor" href="#23-&#x7A33;&#x5B9A;&#x6027;"><i class="fa fa-link" aria-hidden="true"></i></a>2.3 &#x7A33;&#x5B9A;&#x6027;</h3>
<ul>
<li>&#x7A33;&#x5B9A;&#xFF1A;&#x5982;&#x679C;&#x5F85;&#x6392;&#x5E8F;&#x7684;&#x5E8F;&#x5217;&#x4E2D;&#x5B58;&#x5728;&#x503C;<code>&#x76F8;&#x7B49;</code>&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x7ECF;&#x8FC7;&#x6392;&#x5E8F;&#x4E4B;&#x540E;&#xFF0C;&#x76F8;&#x7B49;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x539F;&#x6709;&#x7684;&#x5148;&#x540E;&#x987A;&#x5E8F;<code>&#x4E0D;&#x53D8;</code>&#x3002;
&#x6BD4;&#x5982;&#xFF1A; a &#x539F;&#x672C;&#x5728; b &#x524D;&#x9762;&#xFF0C;&#x800C; a = b&#xFF0C;&#x6392;&#x5E8F;&#x4E4B;&#x540E;&#xFF0C;a &#x4ECD;&#x7136;&#x5728; b &#x7684;&#x524D;&#x9762;&#xFF1B; </li>
<li>&#x4E0D;&#x7A33;&#x5B9A;&#xFF1A;&#x5982;&#x679C;&#x5F85;&#x6392;&#x5E8F;&#x7684;&#x5E8F;&#x5217;&#x4E2D;&#x5B58;&#x5728;&#x503C;<code>&#x76F8;&#x7B49;</code>&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x7ECF;&#x8FC7;&#x6392;&#x5E8F;&#x4E4B;&#x540E;&#xFF0C;&#x76F8;&#x7B49;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x539F;&#x6709;&#x7684;&#x5148;&#x540E;&#x987A;&#x5E8F;<code>&#x6539;&#x53D8;</code>&#x3002;
&#x6BD4;&#x5982;&#xFF1A;a &#x539F;&#x672C;&#x5728; b &#x7684;&#x524D;&#x9762;&#xFF0C;&#x800C; a = b&#xFF0C;&#x6392;&#x5E8F;&#x4E4B;&#x540E;&#xFF0C; a &#x5728; b &#x7684;&#x540E;&#x9762;&#xFF1B;</li>
</ul>
<h2 id="3-&#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;"><a name="3-&#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;" class="anchor-navigation-ex-anchor" href="#3-&#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;"><i class="fa fa-link" aria-hidden="true"></i></a>3. &#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;</h2>
<h3 id="31-&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#xFF08;bubble-sort&#xFF09;"><a name="31-&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#xFF08;bubble-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#31-&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#xFF08;bubble-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.1 &#x5192;&#x6CE1;&#x6392;&#x5E8F;&#xFF08;Bubble Sort&#xFF09;</h3>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-d6851592702b589c.gif?imageMogr2/auto-orient/strip" alt="&#x5192;&#x6CE1;"></p>
<p><strong>&#x601D;&#x60F3;</strong></p>
<ul>
<li>&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x53EA;&#x4F1A;&#x64CD;&#x4F5C;&#x76F8;&#x90BB;&#x7684;&#x4E24;&#x4E2A;&#x6570;&#x636E;&#x3002;</li>
<li>&#x6BCF;&#x6B21;&#x5192;&#x6CE1;&#x64CD;&#x4F5C;&#x90FD;&#x4F1A;&#x5BF9;&#x76F8;&#x90BB;&#x7684;&#x4E24;&#x4E2A;&#x5143;&#x7D20;&#x8FDB;&#x884C;&#x6BD4;&#x8F83;&#xFF0C;&#x770B;&#x662F;&#x5426;&#x6EE1;&#x8DB3;&#x5927;&#x5C0F;&#x5173;&#x7CFB;&#x8981;&#x6C42;&#x3002;&#x5982;&#x679C;&#x4E0D;&#x6EE1;&#x8DB3;&#x5C31;&#x8BA9;&#x5B83;&#x4FE9;&#x4E92;&#x6362;&#x3002;</li>
<li>&#x4E00;&#x6B21;&#x5192;&#x6CE1;&#x4F1A;&#x8BA9;&#x81F3;&#x5C11;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x79FB;&#x52A8;&#x5230;&#x5B83;&#x5E94;&#x8BE5;&#x5728;&#x7684;&#x4F4D;&#x7F6E;&#xFF0C;&#x91CD;&#x590D; n &#x6B21;&#xFF0C;&#x5C31;&#x5B8C;&#x6210;&#x4E86; n &#x4E2A;&#x6570;&#x636E;&#x7684;&#x6392;&#x5E8F;&#x5DE5;&#x4F5C;&#x3002;</li>
</ul>
<p><strong>&#x7279;&#x70B9;</strong></p>
<ul>
<li>&#x4F18;&#x70B9;&#xFF1A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x57FA;&#x7840;&#xFF0C;&#x7B80;&#x5355;&#x5B9E;&#x7528;&#x6613;&#x4E8E;&#x7406;&#x89E3;&#x3002;</li>
<li>&#x7F3A;&#x70B9;&#xFF1A;&#x6BD4;&#x8F83;&#x6B21;&#x6570;&#x591A;&#xFF0C;&#x6548;&#x7387;&#x8F83;&#x4F4E;&#x3002;</li>
</ul>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<pre><code class="lang-javascript">// &#x5192;&#x6CE1;&#x6392;&#x5E8F;&#xFF08;&#x672A;&#x4F18;&#x5316;&#xFF09;
const bubbleSort = arr =&gt; {
    console.time(&apos;&#x6539;&#x8FDB;&#x524D;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    const length = arr.length;
    if (length &lt;= 1) return;
    // i &lt; length - 1 &#x662F;&#x56E0;&#x4E3A;&#x5916;&#x5C42;&#x53EA;&#x9700;&#x8981; length-1 &#x6B21;&#x5C31;&#x6392;&#x597D;&#x4E86;&#xFF0C;&#x7B2C; length &#x6B21;&#x6BD4;&#x8F83;&#x662F;&#x591A;&#x4F59;&#x7684;&#x3002;
    for (let i = 0; i &lt; length - 1; i++) {
        // j &lt; length - i - 1 &#x662F;&#x56E0;&#x4E3A;&#x5185;&#x5C42;&#x7684; length-i-1 &#x5230; length-1 &#x7684;&#x4F4D;&#x7F6E;&#x5DF2;&#x7ECF;&#x6392;&#x597D;&#x4E86;&#xFF0C;&#x4E0D;&#x9700;&#x8981;&#x518D;&#x6BD4;&#x8F83;&#x4E00;&#x6B21;&#x3002;
        for (let j = 0; j &lt; length - i - 1; j++) {
            if (arr[j] &gt; arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(&apos;&#x6539;&#x8FDB;&#x524D; arr :&apos;, arr);
    console.timeEnd(&apos;&#x6539;&#x8FDB;&#x524D;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
};
</code></pre>
<p>&#x4F18;&#x5316;&#xFF1A;&#x5F53;&#x67D0;&#x6B21;&#x5192;&#x6CE1;&#x64CD;&#x4F5C;&#x5DF2;&#x7ECF;&#x6CA1;&#x6709;&#x6570;&#x636E;&#x4EA4;&#x6362;&#x65F6;&#xFF0C;&#x8BF4;&#x660E;&#x5DF2;&#x7ECF;&#x8FBE;&#x5230;&#x5B8C;&#x5168;&#x6709;&#x5E8F;&#xFF0C;&#x4E0D;&#x7528;&#x518D;&#x7EE7;&#x7EED;&#x6267;&#x884C;&#x540E;&#x7EED;&#x7684;&#x5192;&#x6CE1;&#x64CD;&#x4F5C;&#x3002;</p>
<pre><code>// &#x5192;&#x6CE1;&#x6392;&#x5E8F;&#xFF08;&#x5DF2;&#x4F18;&#x5316;&#xFF09;
const bubbleSort2 = arr =&gt; {
    console.time(&apos;&#x6539;&#x8FDB;&#x540E;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    const length = arr.length;
    if (length &lt;= 1) return;
    // i &lt; length - 1 &#x662F;&#x56E0;&#x4E3A;&#x5916;&#x5C42;&#x53EA;&#x9700;&#x8981; length-1 &#x6B21;&#x5C31;&#x6392;&#x597D;&#x4E86;&#xFF0C;&#x7B2C; length &#x6B21;&#x6BD4;&#x8F83;&#x662F;&#x591A;&#x4F59;&#x7684;&#x3002;
    for (let i = 0; i &lt; length - 1; i++) {
        let hasChange = false; // &#x63D0;&#x524D;&#x9000;&#x51FA;&#x5192;&#x6CE1;&#x5FAA;&#x73AF;&#x7684;&#x6807;&#x5FD7;&#x4F4D;
        // j &lt; length - i - 1 &#x662F;&#x56E0;&#x4E3A;&#x5185;&#x5C42;&#x7684; length-i-1 &#x5230; length-1 &#x7684;&#x4F4D;&#x7F6E;&#x5DF2;&#x7ECF;&#x6392;&#x597D;&#x4E86;&#xFF0C;&#x4E0D;&#x9700;&#x8981;&#x518D;&#x6BD4;&#x8F83;&#x4E00;&#x6B21;&#x3002;
        for (let j = 0; j &lt; length - i - 1; j++) {
            if (arr[j] &gt; arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                hasChange = true; // &#x8868;&#x793A;&#x6709;&#x6570;&#x636E;&#x4EA4;&#x6362;
            }
        }

        if (!hasChange) break; // &#x5982;&#x679C; false &#x8BF4;&#x660E;&#x6240;&#x6709;&#x5143;&#x7D20;&#x5DF2;&#x7ECF;&#x5230;&#x4F4D;&#xFF0C;&#x6CA1;&#x6709;&#x6570;&#x636E;&#x4EA4;&#x6362;&#xFF0C;&#x63D0;&#x524D;&#x9000;&#x51FA;
    }
    console.log(&apos;&#x6539;&#x8FDB;&#x540E; arr :&apos;, arr);
    console.timeEnd(&apos;&#x6539;&#x8FDB;&#x540E;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
};
</code></pre><p><strong>&#x6D4B;&#x8BD5;</strong></p>
<pre><code>// &#x6D4B;&#x8BD5;
const arr = [7, 8, 4, 5, 6, 3, 2, 1];
bubbleSort(arr);
// &#x6539;&#x8FDB;&#x524D; arr : [1, 2, 3, 4, 5, 6, 7, 8]
// &#x6539;&#x8FDB;&#x524D;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x8017;&#x65F6;: 0.43798828125ms

const arr2 = [7, 8, 4, 5, 6, 3, 2, 1];
bubbleSort2(arr2);
// &#x6539;&#x8FDB;&#x540E; arr : [1, 2, 3, 4, 5, 6, 7, 8]
// &#x6539;&#x8FDB;&#x540E;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x8017;&#x65F6;: 0.318115234375ms
</code></pre><p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li>&#x7B2C;&#x4E00;&#xFF0C;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x5192;&#x6CE1;&#x7684;&#x8FC7;&#x7A0B;&#x53EA;&#x6D89;&#x53CA;&#x76F8;&#x90BB;&#x6570;&#x636E;&#x7684;&#x4EA4;&#x6362;&#x64CD;&#x4F5C;&#xFF0C;&#x53EA;&#x9700;&#x8981;&#x5E38;&#x91CF;&#x7EA7;&#x7684;&#x4E34;&#x65F6;&#x7A7A;&#x95F4;&#xFF0C;&#x6240;&#x4EE5;&#x5B83;&#x7684;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(1)&#xFF0C;&#x662F;&#x4E00;&#x4E2A;<code>&#x539F;&#x5730;</code>&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
<li>&#x7B2C;&#x4E8C;&#xFF0C;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x5728;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x4E2D;&#xFF0C;&#x53EA;&#x6709;&#x4EA4;&#x6362;&#x624D;&#x53EF;&#x4EE5;&#x6539;&#x53D8;&#x4E24;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x524D;&#x540E;&#x987A;&#x5E8F;&#x3002;
&#x4E3A;&#x4E86;&#x4FDD;&#x8BC1;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x7A33;&#x5B9A;&#x6027;&#xFF0C;&#x5F53;&#x6709;&#x76F8;&#x90BB;&#x7684;&#x4E24;&#x4E2A;&#x5143;&#x7D20;&#x5927;&#x5C0F;&#x76F8;&#x7B49;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x6211;&#x4EEC;&#x4E0D;&#x505A;&#x4EA4;&#x6362;&#xFF0C;&#x76F8;&#x540C;&#x5927;&#x5C0F;&#x7684;&#x6570;&#x636E;&#x5728;&#x6392;&#x5E8F;&#x524D;&#x540E;&#x4E0D;&#x4F1A;&#x6539;&#x53D8;&#x987A;&#x5E8F;&#x3002;
&#x6240;&#x4EE5;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x662F;<code>&#x7A33;&#x5B9A;</code>&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
<li>&#x7B2C;&#x4E09;&#xFF0C;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n)&#xFF0C;&#x5F53;&#x6570;&#x636E;&#x5DF2;&#x7ECF;&#x662F;&#x6B63;&#x5E8F;&#x65F6;&#x3002;
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n<sup>2</sup>)&#xFF0C;&#x5F53;&#x6570;&#x636E;&#x662F;&#x53CD;&#x5E8F;&#x65F6;&#x3002;
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n<sup>2</sup>)&#x3002;</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-68d55469ac439bc6.gif?imageMogr2/auto-orient/strip" alt="&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x52A8;&#x753B;"></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-3948de96d4a28530.gif?imageMogr2/auto-orient/strip" alt="&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x52A8;&#x753B;"></p>
<h3 id="32-&#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF08;insertion-sort&#xFF09;"><a name="32-&#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF08;insertion-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#32-&#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF08;insertion-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.2 &#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF08;Insertion Sort&#xFF09;</h3>
<p>&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x53C8;&#x4E3A;&#x5206;&#x4E3A; <strong>&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;</strong> &#x548C;&#x4F18;&#x5316;&#x540E;&#x7684; <strong>&#x62C6;&#x534A;&#x63D2;&#x5165;&#x6392;&#x5E8F;</strong> &#x4E0E; <strong>&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</strong>&#xFF0C;&#x6211;&#x4EEC;&#x901A;&#x5E38;&#x8BF4;&#x7684;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x662F;&#x6307;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x3002;</p>
<p><strong>&#x4E00;&#x3001;&#x76F4;&#x63A5;&#x63D2;&#x5165;</strong></p>
<p><strong>&#x601D;&#x60F3;</strong></p>
<p>&#x4E00;&#x822C;&#x4EBA;&#x6253;&#x6251;&#x514B;&#x724C;&#xFF0C;&#x6574;&#x7406;&#x724C;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x90FD;&#x662F;&#x6309;&#x724C;&#x7684;&#x5927;&#x5C0F;&#xFF08;&#x4ECE;&#x5C0F;&#x5230;&#x5927;&#x6216;&#x8005;&#x4ECE;&#x5927;&#x5230;&#x5C0F;&#xFF09;&#x6574;&#x7406;&#x724C;&#x7684;&#xFF0C;&#x90A3;&#x6BCF;&#x6478;&#x4E00;&#x5F20;&#x65B0;&#x724C;&#xFF0C;&#x5C31;&#x626B;&#x63CF;&#x81EA;&#x5DF1;&#x7684;&#x724C;&#xFF0C;&#x628A;&#x65B0;&#x724C;&#x63D2;&#x5165;&#x5230;&#x76F8;&#x5E94;&#x7684;&#x4F4D;&#x7F6E;&#x3002;</p>
<p>&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x7684;&#x5DE5;&#x4F5C;&#x539F;&#x7406;&#xFF1A;&#x901A;&#x8FC7;&#x6784;&#x5EFA;&#x6709;&#x5E8F;&#x5E8F;&#x5217;&#xFF0C;&#x5BF9;&#x4E8E;&#x672A;&#x6392;&#x5E8F;&#x6570;&#x636E;&#xFF0C;&#x5728;&#x5DF2;&#x6392;&#x5E8F;&#x5E8F;&#x5217;&#x4E2D;&#x4ECE;&#x540E;&#x5411;&#x524D;&#x626B;&#x63CF;&#xFF0C;&#x627E;&#x5230;&#x76F8;&#x5E94;&#x4F4D;&#x7F6E;&#x5E76;&#x63D2;&#x5165;&#x3002;</p>
<p><strong>&#x6B65;&#x9AA4;</strong></p>
<ul>
<li>&#x4ECE;&#x7B2C;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x5F00;&#x59CB;&#xFF0C;&#x8BE5;&#x5143;&#x7D20;&#x53EF;&#x4EE5;&#x8BA4;&#x4E3A;&#x5DF2;&#x7ECF;&#x88AB;&#x6392;&#x5E8F;&#xFF1B;</li>
<li>&#x53D6;&#x51FA;&#x4E0B;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x5728;&#x5DF2;&#x7ECF;&#x6392;&#x5E8F;&#x7684;&#x5143;&#x7D20;&#x5E8F;&#x5217;&#x4E2D;&#x4ECE;&#x540E;&#x5411;&#x524D;&#x626B;&#x63CF;&#xFF1B;</li>
<li>&#x5982;&#x679C;&#x8BE5;&#x5143;&#x7D20;&#xFF08;&#x5DF2;&#x6392;&#x5E8F;&#xFF09;&#x5927;&#x4E8E;&#x65B0;&#x5143;&#x7D20;&#xFF0C;&#x5C06;&#x8BE5;&#x5143;&#x7D20;&#x79FB;&#x5230;&#x4E0B;&#x4E00;&#x4F4D;&#x7F6E;&#xFF1B;</li>
<li>&#x91CD;&#x590D;&#x6B65;&#x9AA4; 3&#xFF0C;&#x76F4;&#x5230;&#x627E;&#x5230;&#x5DF2;&#x6392;&#x5E8F;&#x7684;&#x5143;&#x7D20;&#x5C0F;&#x4E8E;&#x6216;&#x8005;&#x7B49;&#x4E8E;&#x65B0;&#x5143;&#x7D20;&#x7684;&#x4F4D;&#x7F6E;&#xFF1B;</li>
<li>&#x5C06;&#x65B0;&#x5143;&#x7D20;&#x63D2;&#x5165;&#x5230;&#x8BE5;&#x4F4D;&#x7F6E;&#x540E;&#xFF1B;</li>
<li>&#x91CD;&#x590D;&#x6B65;&#x9AA4; 2 ~ 5&#x3002;</li>
</ul>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<pre><code>// &#x63D2;&#x5165;&#x6392;&#x5E8F;
const insertionSort = array =&gt; {
    const len = array.length;
    if (len &lt;= 1) return

    let preIndex, current;
    for (let i = 1; i &lt; len; i++) {
        preIndex = i - 1; //&#x5F85;&#x6BD4;&#x8F83;&#x5143;&#x7D20;&#x7684;&#x4E0B;&#x6807;
        current = array[i]; //&#x5F53;&#x524D;&#x5143;&#x7D20;
        while (preIndex &gt;= 0 &amp;&amp; array[preIndex] &gt; current) {
            //&#x524D;&#x7F6E;&#x6761;&#x4EF6;&#x4E4B;&#x4E00;: &#x5F85;&#x6BD4;&#x8F83;&#x5143;&#x7D20;&#x6BD4;&#x5F53;&#x524D;&#x5143;&#x7D20;&#x5927;
            array[preIndex + 1] = array[preIndex]; //&#x5C06;&#x5F85;&#x6BD4;&#x8F83;&#x5143;&#x7D20;&#x540E;&#x79FB;&#x4E00;&#x4F4D;
            preIndex--; //&#x6E38;&#x6807;&#x524D;&#x79FB;&#x4E00;&#x4F4D;
        }
        if (preIndex + 1 != i) {
            //&#x907F;&#x514D;&#x540C;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x8D4B;&#x503C;&#x7ED9;&#x81EA;&#x8EAB;
            array[preIndex + 1] = current; //&#x5C06;&#x5F53;&#x524D;&#x5143;&#x7D20;&#x63D2;&#x5165;&#x9884;&#x7559;&#x7A7A;&#x4F4D;
            console.log(&apos;array :&apos;, array);
        }
    }
    return array;
};
</code></pre><p>&#x6D4B;&#x8BD5;</p>
<pre><code>// &#x6D4B;&#x8BD5;
const array = [5, 4, 3, 2, 1];
console.log(&quot;&#x539F;&#x59CB; array :&quot;, array);
insertionSort(array);
// &#x539F;&#x59CB; array:    [5, 4, 3, 2, 1]
// array:           [4, 5, 3, 2, 1]
// array:           [3, 4, 5, 2, 1]
// array:          [2, 3, 4, 5, 1]
// array:           [1, 2, 3, 4, 5]
</code></pre><p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li>&#x7B2C;&#x4E00;&#xFF0C;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x8FD0;&#x884C;&#x5E76;&#x4E0D;&#x9700;&#x8981;&#x989D;&#x5916;&#x7684;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;&#xFF0C;&#x6240;&#x4EE5;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; O(1)&#xFF0C;&#x6240;&#x4EE5;&#xFF0C;&#x8FD9;&#x662F;&#x4E00;&#x4E2A;<code>&#x539F;&#x5730;</code>&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
<li>&#x7B2C;&#x4E8C;&#xFF0C;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x5728;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x4E2D;&#xFF0C;&#x5BF9;&#x4E8E;&#x503C;&#x76F8;&#x540C;&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x9009;&#x62E9;&#x5C06;&#x540E;&#x9762;&#x51FA;&#x73B0;&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x63D2;&#x5165;&#x5230;&#x524D;&#x9762;&#x51FA;&#x73B0;&#x5143;&#x7D20;&#x7684;&#x540E;&#x9762;&#xFF0C;&#x8FD9;&#x6837;&#x5C31;&#x53EF;&#x4EE5;&#x4FDD;&#x6301;&#x539F;&#x6709;&#x7684;&#x524D;&#x540E;&#x987A;&#x5E8F;&#x4E0D;&#x53D8;&#xFF0C;&#x6240;&#x4EE5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x662F;<code>&#x7A33;&#x5B9A;</code>&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
<li>&#x7B2C;&#x4E09;&#xFF0C;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n)&#xFF0C;&#x5F53;&#x6570;&#x636E;&#x5DF2;&#x7ECF;&#x662F;&#x6B63;&#x5E8F;&#x65F6;&#x3002;
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n<sup>2</sup>)&#xFF0C;&#x5F53;&#x6570;&#x636E;&#x662F;&#x53CD;&#x5E8F;&#x65F6;&#x3002;
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n<sup>2</sup>)&#x3002;</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-8ba117506372e97e.gif?imageMogr2/auto-orient/strip" alt="insertion-sort.gif"></p>
<p><strong>&#x4E8C;&#x3001;&#x62C6;&#x534A;&#x63D2;&#x5165;</strong></p>
<p>&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x4E5F;&#x6709;&#x4E00;&#x79CD;&#x4F18;&#x5316;&#x7B97;&#x6CD5;&#xFF0C;&#x53EB;&#x505A;<code>&#x62C6;&#x534A;&#x63D2;&#x5165;</code>&#x3002;</p>
<p><strong>&#x601D;&#x60F3;</strong></p>
<p>&#x6298;&#x534A;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x662F;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x7684;&#x5347;&#x7EA7;&#x7248;&#xFF0C;&#x9274;&#x4E8E;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x7B2C;&#x4E00;&#x90E8;&#x5206;&#x4E3A;&#x5DF2;&#x6392;&#x597D;&#x5E8F;&#x7684;&#x6570;&#x7EC4;&#xFF0C;&#x6211;&#x4EEC;&#x4E0D;&#x5FC5;&#x6309;&#x987A;&#x5E8F;&#x4F9D;&#x6B21;&#x5BFB;&#x627E;&#x63D2;&#x5165;&#x70B9;&#xFF0C;&#x53EA;&#x9700;&#x6BD4;&#x8F83;&#x5B83;&#x4EEC;&#x7684;&#x4E2D;&#x95F4;&#x503C;&#x4E0E;&#x5F85;&#x63D2;&#x5165;&#x5143;&#x7D20;&#x7684;&#x5927;&#x5C0F;&#x5373;&#x53EF;&#x3002;</p>
<p><strong>&#x6B65;&#x9AA4;</strong></p>
<ul>
<li>&#x53D6; 0 ~ i-1 &#x7684;&#x4E2D;&#x95F4;&#x70B9; ( m = (i-1) &gt;&gt; 1 )&#xFF0C;array[i] &#x4E0E; array[m] &#x8FDB;&#x884C;&#x6BD4;&#x8F83;&#xFF0C;&#x82E5; array[i]  &lt;  array[m]&#xFF0C;&#x5219;&#x8BF4;&#x660E;&#x5F85;&#x63D2;&#x5165;&#x7684;&#x5143;&#x7D20; array[i]  &#x5E94;&#x8BE5;&#x5904;&#x4E8E;&#x6570;&#x7EC4;&#x7684; 0 ~ m &#x7D22;&#x5F15;&#x4E4B;&#x95F4;&#xFF1B;&#x53CD;&#x4E4B;&#xFF0C;&#x5219;&#x8BF4;&#x660E;&#x5B83;&#x5E94;&#x8BE5;&#x5904;&#x4E8E;&#x6570;&#x7EC4;&#x7684; m ~ i-1 &#x7D22;&#x5F15;&#x4E4B;&#x95F4;&#x3002;</li>
<li>&#x91CD;&#x590D;&#x6B65;&#x9AA4; 1&#xFF0C;&#x6BCF;&#x6B21;&#x7F29;&#x5C0F;&#x4E00;&#x534A;&#x7684;&#x67E5;&#x627E;&#x8303;&#x56F4;&#xFF0C;&#x76F4;&#x81F3;&#x627E;&#x5230;&#x63D2;&#x5165;&#x7684;&#x4F4D;&#x7F6E;&#x3002;</li>
<li>&#x5C06;&#x6570;&#x7EC4;&#x4E2D;&#x63D2;&#x5165;&#x4F4D;&#x7F6E;&#x4E4B;&#x540E;&#x7684;&#x5143;&#x7D20;&#x5168;&#x90E8;&#x540E;&#x79FB;&#x4E00;&#x4F4D;&#x3002;</li>
<li>&#x5728;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;&#x63D2;&#x5165;&#x7B2C; i &#x4E2A;&#x5143;&#x7D20;&#x3002;</li>
</ul>
<blockquote>
<p>&#x6CE8;&#xFF1A;x &gt;&gt; 1 &#x662F;&#x4F4D;&#x8FD0;&#x7B97;&#x4E2D;&#x7684;&#x53F3;&#x79FB;&#x8FD0;&#x7B97;&#xFF0C;&#x8868;&#x793A;&#x53F3;&#x79FB;&#x4E00;&#x4F4D;&#xFF0C;&#x7B49;&#x540C;&#x4E8E; x &#x9664;&#x4EE5; 2 &#x518D;&#x53D6;&#x6574;&#xFF0C;&#x5373; x &gt;&gt; 1 == Math.floor(x/2) &#x3002;</p>
</blockquote>
<pre><code>// &#x6298;&#x534A;&#x63D2;&#x5165;&#x6392;&#x5E8F;
const binaryInsertionSort = array =&gt; {
    const len = array.length;
    if (len &lt;= 1) return;

    let current, i, j, low, high, m;
    for (i = 1; i &lt; len; i++) {
        low = 0;
        high = i - 1;
        current = array[i];

        while (low &lt;= high) {
            //&#x6B65;&#x9AA4; 1 &amp; 2 : &#x6298;&#x534A;&#x67E5;&#x627E;
            m = (low + high) &gt;&gt; 1; // &#x6CE8;: x&gt;&gt;1 &#x662F;&#x4F4D;&#x8FD0;&#x7B97;&#x4E2D;&#x7684;&#x53F3;&#x79FB;&#x8FD0;&#x7B97;, &#x8868;&#x793A;&#x53F3;&#x79FB;&#x4E00;&#x4F4D;, &#x7B49;&#x540C;&#x4E8E; x &#x9664;&#x4EE5; 2 &#x518D;&#x53D6;&#x6574;, &#x5373; x&gt;&gt;1 == Math.floor(x/2) .
            if (array[i] &gt;= array[m]) {
                //&#x503C;&#x76F8;&#x540C;&#x65F6;, &#x5207;&#x6362;&#x5230;&#x9AD8;&#x534A;&#x533A;&#xFF0C;&#x4FDD;&#x8BC1;&#x7A33;&#x5B9A;&#x6027;
                low = m + 1; //&#x63D2;&#x5165;&#x70B9;&#x5728;&#x9AD8;&#x534A;&#x533A;
            } else {
                high = m - 1; //&#x63D2;&#x5165;&#x70B9;&#x5728;&#x4F4E;&#x534A;&#x533A;
            }
        }
        for (j = i; j &gt; low; j--) {
            //&#x6B65;&#x9AA4; 3: &#x63D2;&#x5165;&#x4F4D;&#x7F6E;&#x4E4B;&#x540E;&#x7684;&#x5143;&#x7D20;&#x5168;&#x90E8;&#x540E;&#x79FB;&#x4E00;&#x4F4D;
            array[j] = array[j - 1];
            console.log(&apos;array2 :&apos;, JSON.parse(JSON.stringify(array)));
        }
        array[low] = current; //&#x6B65;&#x9AA4; 4: &#x63D2;&#x5165;&#x8BE5;&#x5143;&#x7D20;
    }
    console.log(&apos;array2 :&apos;, JSON.parse(JSON.stringify(array)));
    return array;
};
</code></pre><p>&#x6D4B;&#x8BD5;</p>
<pre><code>const array2 = [5, 4, 3, 2, 1];
console.log(&apos;&#x539F;&#x59CB; array2:&apos;, array2);
binaryInsertionSort(array2);
// &#x539F;&#x59CB; array2:  [5, 4, 3, 2, 1]
// array2 :     [5, 5, 3, 2, 1]
// array2 :     [4, 5, 5, 2, 1]
// array2 :     [4, 4, 5, 2, 1]
// array2 :     [3, 4, 5, 5, 1]
// array2 :     [3, 4, 4, 5, 1]
// array2 :     [3, 3, 4, 5, 1]
// array2 :     [2, 3, 4, 5, 5]
// array2 :     [2, 3, 4, 4, 5]
// array2 :     [2, 3, 3, 4, 5]
// array2 :     [2, 2, 3, 4, 5]
// array2 :     [1, 2, 3, 4, 5]
</code></pre><p><code>&#x6CE8;&#x610F;</code>&#xFF1A;&#x548C;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x7C7B;&#x4F3C;&#xFF0C;&#x6298;&#x534A;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x6BCF;&#x6B21;&#x4EA4;&#x6362;&#x7684;&#x662F;&#x76F8;&#x90BB;&#x7684;&#x4E14;&#x503C;&#x4E3A;&#x4E0D;&#x540C;&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x5B83;&#x5E76;&#x4E0D;&#x4F1A;&#x6539;&#x53D8;&#x503C;&#x76F8;&#x540C;&#x7684;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x7684;&#x987A;&#x5E8F;&#xFF0C;&#x56E0;&#x6B64;&#x5B83;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x3002;</p>
<p><strong>&#x4E09;&#x3001;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</strong></p>
<p>&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x662F;&#x4E00;&#x4E2A;&#x5E73;&#x5747;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(n log n) &#x7684;&#x7B97;&#x6CD5;&#xFF0C;&#x4F1A;&#x5728;&#x4E0B;&#x4E00;&#x4E2A;&#x7AE0;&#x8282;&#x548C; &#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x3001;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x3001;&#x5806;&#x6392;&#x5E8F; &#x4E00;&#x8D77;&#x8BB2;&#xFF0C;&#x672C;&#x6587;&#x5C31;&#x4E0D;&#x5C55;&#x5F00;&#x4E86;&#x3002;</p>
<h3 id="33-&#x9009;&#x62E9;&#x6392;&#x5E8F;&#xFF08;selection-sort&#xFF09;"><a name="33-&#x9009;&#x62E9;&#x6392;&#x5E8F;&#xFF08;selection-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#33-&#x9009;&#x62E9;&#x6392;&#x5E8F;&#xFF08;selection-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.3 &#x9009;&#x62E9;&#x6392;&#x5E8F;&#xFF08;Selection Sort&#xFF09;</h3>
<p><strong>&#x601D;&#x8DEF;</strong></p>
<p>&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x5B9E;&#x73B0;&#x601D;&#x8DEF;&#x6709;&#x70B9;&#x7C7B;&#x4F3C;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF0C;&#x4E5F;&#x5206;&#x5DF2;&#x6392;&#x5E8F;&#x533A;&#x95F4;&#x548C;&#x672A;&#x6392;&#x5E8F;&#x533A;&#x95F4;&#x3002;&#x4F46;&#x662F;&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x6BCF;&#x6B21;&#x4F1A;&#x4ECE;&#x672A;&#x6392;&#x5E8F;&#x533A;&#x95F4;&#x4E2D;&#x627E;&#x5230;&#x6700;&#x5C0F;&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x5C06;&#x5176;&#x653E;&#x5230;&#x5DF2;&#x6392;&#x5E8F;&#x533A;&#x95F4;&#x7684;&#x672B;&#x5C3E;&#x3002;</p>
<p><strong>&#x6B65;&#x9AA4;</strong></p>
<ol>
<li>&#x9996;&#x5148;&#x5728;&#x672A;&#x6392;&#x5E8F;&#x5E8F;&#x5217;&#x4E2D;&#x627E;&#x5230;&#x6700;&#x5C0F;&#xFF08;&#x5927;&#xFF09;&#x5143;&#x7D20;&#xFF0C;&#x5B58;&#x653E;&#x5230;&#x6392;&#x5E8F;&#x5E8F;&#x5217;&#x7684;&#x8D77;&#x59CB;&#x4F4D;&#x7F6E;&#x3002;</li>
<li>&#x518D;&#x4ECE;&#x5269;&#x4F59;&#x672A;&#x6392;&#x5E8F;&#x5143;&#x7D20;&#x4E2D;&#x7EE7;&#x7EED;&#x5BFB;&#x627E;&#x6700;&#x5C0F;&#xFF08;&#x5927;&#xFF09;&#x5143;&#x7D20;&#xFF0C;&#x7136;&#x540E;&#x653E;&#x5230;&#x5DF2;&#x6392;&#x5E8F;&#x5E8F;&#x5217;&#x7684;&#x672B;&#x5C3E;&#x3002;</li>
<li>&#x91CD;&#x590D;&#x7B2C;&#x4E8C;&#x6B65;&#xFF0C;&#x76F4;&#x5230;&#x6240;&#x6709;&#x5143;&#x7D20;&#x5747;&#x6392;&#x5E8F;&#x5B8C;&#x6BD5;&#x3002;</li>
</ol>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<pre><code>const selectionSort = array =&gt; {
    const len = array.length;
    let minIndex, temp;
    for (let i = 0; i &lt; len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j &lt; len; j++) {
            if (array[j] &lt; array[minIndex]) {
                // &#x5BFB;&#x627E;&#x6700;&#x5C0F;&#x7684;&#x6570;
                minIndex = j; // &#x5C06;&#x6700;&#x5C0F;&#x6570;&#x7684;&#x7D22;&#x5F15;&#x4FDD;&#x5B58;
            }
        }
        temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
        console.log(&apos;array: &apos;, array);
    }
    return array;
};
</code></pre><p>&#x6D4B;&#x8BD5;</p>
<pre><code>// &#x6D4B;&#x8BD5;
const array = [5, 4, 3, 2, 1];
console.log(&apos;&#x539F;&#x59CB;array:&apos;, array);
selectionSort(array);
// &#x539F;&#x59CB; array:  [5, 4, 3, 2, 1]
// array:           [1, 4, 3, 2, 5]
// array:           [1, 2, 3, 4, 5]
// array:          [1, 2, 3, 4, 5]
// array:           [1, 2, 3, 4, 5]
</code></pre><p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li>&#x7B2C;&#x4E00;&#xFF0C;&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(1)&#xFF0C;&#x662F;&#x4E00;&#x79CD;<code>&#x539F;&#x5730;</code>&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
<li>&#x7B2C;&#x4E8C;&#xFF0C;&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x6BCF;&#x6B21;&#x90FD;&#x8981;&#x627E;&#x5269;&#x4F59;&#x672A;&#x6392;&#x5E8F;&#x5143;&#x7D20;&#x4E2D;&#x7684;&#x6700;&#x5C0F;&#x503C;&#xFF0C;&#x5E76;&#x548C;&#x524D;&#x9762;&#x7684;&#x5143;&#x7D20;&#x4EA4;&#x6362;&#x4F4D;&#x7F6E;&#xFF0C;&#x8FD9;&#x6837;&#x7834;&#x574F;&#x4E86;&#x7A33;&#x5B9A;&#x6027;&#x3002;&#x6240;&#x4EE5;&#xFF0C;&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x662F;&#x4E00;&#x79CD;<code>&#x4E0D;&#x7A33;&#x5B9A;</code>&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
<li>&#x7B2C;&#x4E09;&#xFF0C;&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x65E0;&#x8BBA;&#x662F;&#x6B63;&#x5E8F;&#x8FD8;&#x662F;&#x9006;&#x5E8F;&#xFF0C;&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x90FD;&#x4F1A;&#x904D;&#x5386; n<sup>2</sup> / 2 &#x6B21;&#x6765;&#x6392;&#x5E8F;&#xFF0C;&#x6240;&#x4EE5;&#xFF0C;&#x6700;&#x4F73;&#x3001;&#x6700;&#x5DEE;&#x548C;&#x5E73;&#x5747;&#x7684;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x4E00;&#x6837;&#x7684;&#x3002;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n<sup>2</sup>)&#x3002;
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n<sup>2</sup>)&#x3002;
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n<sup>2</sup>)&#x3002;</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-27ddfb636eabff03.gif?imageMogr2/auto-orient/strip" alt="selection-sort.gif"></p>
<h3 id="34-&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#xFF08;merge-sort&#xFF09;"><a name="34-&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#xFF08;merge-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#34-&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#xFF08;merge-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.4 &#x5F52;&#x5E76;&#x6392;&#x5E8F;&#xFF08;Merge Sort&#xFF09;</h3>
<p><strong>&#x601D;&#x60F3;</strong></p>
<p>&#x6392;&#x5E8F;&#x4E00;&#x4E2A;&#x6570;&#x7EC4;&#xFF0C;&#x6211;&#x4EEC;&#x5148;&#x628A;&#x6570;&#x7EC4;&#x4ECE;&#x4E2D;&#x95F4;&#x5206;&#x6210;&#x524D;&#x540E;&#x4E24;&#x90E8;&#x5206;&#xFF0C;&#x7136;&#x540E;&#x5BF9;&#x524D;&#x540E;&#x4E24;&#x90E8;&#x5206;&#x5206;&#x522B;&#x6392;&#x5E8F;&#xFF0C;&#x518D;&#x5C06;&#x6392;&#x597D;&#x5E8F;&#x7684;&#x4E24;&#x90E8;&#x5206;&#x5408;&#x5E76;&#x5728;&#x4E00;&#x8D77;&#xFF0C;&#x8FD9;&#x6837;&#x6574;&#x4E2A;&#x6570;&#x7EC4;&#x5C31;&#x90FD;&#x6709;&#x5E8F;&#x4E86;&#x3002;</p>
<p>&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x91C7;&#x7528;&#x7684;&#x662F;<code>&#x5206;&#x6CBB;&#x601D;&#x60F3;</code>&#x3002;</p>
<p>&#x5206;&#x6CBB;&#xFF0C;&#x987E;&#x540D;&#x601D;&#x4E49;&#xFF0C;&#x5C31;&#x662F;&#x5206;&#x800C;&#x6CBB;&#x4E4B;&#xFF0C;&#x5C06;&#x4E00;&#x4E2A;&#x5927;&#x95EE;&#x9898;&#x5206;&#x89E3;&#x6210;&#x5C0F;&#x7684;&#x5B50;&#x95EE;&#x9898;&#x6765;&#x89E3;&#x51B3;&#x3002;&#x5C0F;&#x7684;&#x5B50;&#x95EE;&#x9898;&#x89E3;&#x51B3;&#x4E86;&#xFF0C;&#x5927;&#x95EE;&#x9898;&#x4E5F;&#x5C31;&#x89E3;&#x51B3;&#x4E86;&#x3002;</p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-a186be41b62d6f65.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="merge-sort-example.png"></p>
<blockquote>
<p>&#x6CE8;&#xFF1A;x &gt;&gt; 1 &#x662F;&#x4F4D;&#x8FD0;&#x7B97;&#x4E2D;&#x7684;&#x53F3;&#x79FB;&#x8FD0;&#x7B97;&#xFF0C;&#x8868;&#x793A;&#x53F3;&#x79FB;&#x4E00;&#x4F4D;&#xFF0C;&#x7B49;&#x540C;&#x4E8E; x &#x9664;&#x4EE5; 2 &#x518D;&#x53D6;&#x6574;&#xFF0C;&#x5373; x &gt;&gt; 1 === Math.floor(x / 2) &#x3002;</p>
</blockquote>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<pre><code class="lang-javascript">const mergeSort = arr =&gt; {
    //&#x91C7;&#x7528;&#x81EA;&#x4E0A;&#x800C;&#x4E0B;&#x7684;&#x9012;&#x5F52;&#x65B9;&#x6CD5;
    const len = arr.length;
    if (len &lt; 2) {
        return arr;
    }
    // length &gt;&gt; 1 &#x548C; Math.floor(len / 2) &#x7B49;&#x4EF7;
    let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle); // &#x62C6;&#x5206;&#x4E3A;&#x4E24;&#x4E2A;&#x5B50;&#x6570;&#x7EC4;
    return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) =&gt; {
    const result = [];

    while (left.length &amp;&amp; right.length) {
        // &#x6CE8;&#x610F;: &#x5224;&#x65AD;&#x7684;&#x6761;&#x4EF6;&#x662F;&#x5C0F;&#x4E8E;&#x6216;&#x7B49;&#x4E8E;&#xFF0C;&#x5982;&#x679C;&#x53EA;&#x662F;&#x5C0F;&#x4E8E;&#xFF0C;&#x90A3;&#x4E48;&#x6392;&#x5E8F;&#x5C06;&#x4E0D;&#x7A33;&#x5B9A;.
        if (left[0] &lt;= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length) result.push(left.shift());

    while (right.length) result.push(right.shift());

    return result;
};
</code></pre>
<p><strong>&#x6D4B;&#x8BD5;</strong></p>
<pre><code class="lang-javascript">// &#x6D4B;&#x8BD5;
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.time(&apos;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
console.log(&apos;arr :&apos;, mergeSort(arr));
console.timeEnd(&apos;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
// arr : [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
// &#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x8017;&#x65F6;: 0.739990234375ms
</code></pre>
<p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li><p>&#x7B2C;&#x4E00;&#xFF0C;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x8FD9;&#x662F;&#x56E0;&#x4E3A;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x7684;&#x5408;&#x5E76;&#x51FD;&#x6570;&#xFF0C;&#x5728;&#x5408;&#x5E76;&#x4E24;&#x4E2A;&#x6709;&#x5E8F;&#x6570;&#x7EC4;&#x4E3A;&#x4E00;&#x4E2A;&#x6709;&#x5E8F;&#x6570;&#x7EC4;&#x65F6;&#xFF0C;&#x9700;&#x8981;&#x501F;&#x52A9;&#x989D;&#x5916;&#x7684;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;&#x3002;
&#x5B9E;&#x9645;&#x4E0A;&#xFF0C;&#x5C3D;&#x7BA1;&#x6BCF;&#x6B21;&#x5408;&#x5E76;&#x64CD;&#x4F5C;&#x90FD;&#x9700;&#x8981;&#x7533;&#x8BF7;&#x989D;&#x5916;&#x7684;&#x5185;&#x5B58;&#x7A7A;&#x95F4;&#xFF0C;&#x4F46;&#x5728;&#x5408;&#x5E76;&#x5B8C;&#x6210;&#x4E4B;&#x540E;&#xFF0C;&#x4E34;&#x65F6;&#x5F00;&#x8F9F;&#x7684;&#x5185;&#x5B58;&#x7A7A;&#x95F4;&#x5C31;&#x88AB;&#x91CA;&#x653E;&#x6389;&#x4E86;&#x3002;&#x5728;&#x4EFB;&#x610F;&#x65F6;&#x523B;&#xFF0C;CPU &#x53EA;&#x4F1A;&#x6709;&#x4E00;&#x4E2A;&#x51FD;&#x6570;&#x5728;&#x6267;&#x884C;&#xFF0C;&#x4E5F;&#x5C31;&#x53EA;&#x4F1A;&#x6709;&#x4E00;&#x4E2A;&#x4E34;&#x65F6;&#x7684;&#x5185;&#x5B58;&#x7A7A;&#x95F4;&#x5728;&#x4F7F;&#x7528;&#x3002;&#x4E34;&#x65F6;&#x5185;&#x5B58;&#x7A7A;&#x95F4;&#x6700;&#x5927;&#x4E5F;&#x4E0D;&#x4F1A;&#x8D85;&#x8FC7; n &#x4E2A;&#x6570;&#x636E;&#x7684;&#x5927;&#x5C0F;&#xFF0C;&#x6240;&#x4EE5;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; O(n)&#x3002;
&#x6240;&#x4EE5;&#xFF0C;&#x5F52;&#x5E76;&#x6392;&#x5E8F;<code>&#x4E0D;&#x662F;</code>&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E8C;&#xFF0C;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
merge &#x65B9;&#x6CD5;&#x91CC;&#x9762;&#x7684; left[0] &lt;= right[0] &#xFF0C;&#x4FDD;&#x8BC1;&#x4E86;&#x503C;&#x76F8;&#x540C;&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x5728;&#x5408;&#x5E76;&#x524D;&#x540E;&#x7684;&#x5148;&#x540E;&#x987A;&#x5E8F;&#x4E0D;&#x53D8;&#x3002;&#x5F52;&#x5E76;&#x6392;&#x5E8F;<code>&#x662F;&#x7A33;&#x5B9A;</code>&#x7684;&#x6392;&#x5E8F;&#x65B9;&#x6CD5;&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E09;&#xFF0C;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x4ECE;&#x6548;&#x7387;&#x4E0A;&#x770B;&#xFF0C;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x53EF;&#x7B97;&#x662F;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x4E2D;&#x7684;<code>&#x4F7C;&#x4F7C;&#x8005;</code>&#x3002;&#x5047;&#x8BBE;&#x6570;&#x7EC4;&#x957F;&#x5EA6;&#x4E3A; n&#xFF0C;&#x90A3;&#x4E48;&#x62C6;&#x5206;&#x6570;&#x7EC4;&#x5171;&#x9700; logn &#x6B65;&#xFF0C;&#x53C8;&#x6BCF;&#x6B65;&#x90FD;&#x662F;&#x4E00;&#x4E2A;&#x666E;&#x901A;&#x7684;&#x5408;&#x5E76;&#x5B50;&#x6570;&#x7EC4;&#x7684;&#x8FC7;&#x7A0B;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(n)&#xFF0C;&#x6545;&#x5176;&#x7EFC;&#x5408;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(n log n)&#x3002;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log n)&#x3002;
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log n)&#x3002;
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log n)&#x3002;</p>
</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-32372625906df3ae.gif?imageMogr2/auto-orient/strip" alt="merge-sort.gif"></p>
<h3 id="35-&#x5FEB;&#x901F;&#x6392;&#x5E8F;-&#xFF08;quick-sort&#xFF09;"><a name="35-&#x5FEB;&#x901F;&#x6392;&#x5E8F;-&#xFF08;quick-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#35-&#x5FEB;&#x901F;&#x6392;&#x5E8F;-&#xFF08;quick-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.5 &#x5FEB;&#x901F;&#x6392;&#x5E8F; &#xFF08;Quick Sort&#xFF09;</h3>
<p>&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x7684;&#x7279;&#x70B9;&#x5C31;&#x662F;&#x5FEB;&#xFF0C;&#x800C;&#x4E14;&#x6548;&#x7387;&#x9AD8;&#xFF01;&#x5B83;&#x662F;&#x5904;&#x7406;&#x5927;&#x6570;&#x636E;&#x6700;&#x5FEB;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x4E4B;&#x4E00;&#x3002;</p>
<p><strong>&#x601D;&#x60F3;</strong></p>
<ul>
<li>&#x5148;&#x627E;&#x5230;&#x4E00;&#x4E2A;&#x57FA;&#x51C6;&#x70B9;&#xFF08;&#x4E00;&#x822C;&#x6307;&#x6570;&#x7EC4;&#x7684;&#x4E2D;&#x90E8;&#xFF09;&#xFF0C;&#x7136;&#x540E;&#x6570;&#x7EC4;&#x88AB;&#x8BE5;&#x57FA;&#x51C6;&#x70B9;&#x5206;&#x4E3A;&#x4E24;&#x90E8;&#x5206;&#xFF0C;&#x4F9D;&#x6B21;&#x4E0E;&#x8BE5;&#x57FA;&#x51C6;&#x70B9;&#x6570;&#x636E;&#x6BD4;&#x8F83;&#xFF0C;&#x5982;&#x679C;&#x6BD4;&#x5B83;&#x5C0F;&#xFF0C;&#x653E;&#x5DE6;&#x8FB9;&#xFF1B;&#x53CD;&#x4E4B;&#xFF0C;&#x653E;&#x53F3;&#x8FB9;&#x3002;</li>
<li>&#x5DE6;&#x53F3;&#x5206;&#x522B;&#x7528;&#x4E00;&#x4E2A;&#x7A7A;&#x6570;&#x7EC4;&#x53BB;&#x5B58;&#x50A8;&#x6BD4;&#x8F83;&#x540E;&#x7684;&#x6570;&#x636E;&#x3002;</li>
<li>&#x6700;&#x540E;&#x9012;&#x5F52;&#x6267;&#x884C;&#x4E0A;&#x8FF0;&#x64CD;&#x4F5C;&#xFF0C;&#x76F4;&#x5230;&#x6570;&#x7EC4;&#x957F;&#x5EA6; &lt;= 1;</li>
</ul>
<p>&#x7279;&#x70B9;&#xFF1A;&#x5FEB;&#x901F;&#xFF0C;&#x5E38;&#x7528;&#x3002;</p>
<p>&#x7F3A;&#x70B9;&#xFF1A;&#x9700;&#x8981;&#x53E6;&#x5916;&#x58F0;&#x660E;&#x4E24;&#x4E2A;&#x6570;&#x7EC4;&#xFF0C;&#x6D6A;&#x8D39;&#x4E86;&#x5185;&#x5B58;&#x7A7A;&#x95F4;&#x8D44;&#x6E90;&#x3002;</p>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<p>&#x65B9;&#x6CD5;&#x4E00;&#xFF1A;</p>
<pre><code class="lang-javascript">const quickSort1 = arr =&gt; {
    if (arr.length &lt;= 1) {
        return arr;
    }
    //&#x53D6;&#x57FA;&#x51C6;&#x70B9;
    const midIndex = Math.floor(arr.length / 2);
    //&#x53D6;&#x57FA;&#x51C6;&#x70B9;&#x7684;&#x503C;&#xFF0C;splice(index,1) &#x5219;&#x8FD4;&#x56DE;&#x7684;&#x662F;&#x542B;&#x6709;&#x88AB;&#x5220;&#x9664;&#x7684;&#x5143;&#x7D20;&#x7684;&#x6570;&#x7EC4;&#x3002;
    const valArr = arr.splice(midIndex, 1);
    const midIndexVal = valArr[0];
    const left = []; //&#x5B58;&#x653E;&#x6BD4;&#x57FA;&#x51C6;&#x70B9;&#x5C0F;&#x7684;&#x6570;&#x7EC4;
    const right = []; //&#x5B58;&#x653E;&#x6BD4;&#x57FA;&#x51C6;&#x70B9;&#x5927;&#x7684;&#x6570;&#x7EC4;
    //&#x904D;&#x5386;&#x6570;&#x7EC4;&#xFF0C;&#x8FDB;&#x884C;&#x5224;&#x65AD;&#x5206;&#x914D;
    for (let i = 0; i &lt; arr.length; i++) {
        if (arr[i] &lt; midIndexVal) {
            left.push(arr[i]); //&#x6BD4;&#x57FA;&#x51C6;&#x70B9;&#x5C0F;&#x7684;&#x653E;&#x5728;&#x5DE6;&#x8FB9;&#x6570;&#x7EC4;
        } else {
            right.push(arr[i]); //&#x6BD4;&#x57FA;&#x51C6;&#x70B9;&#x5927;&#x7684;&#x653E;&#x5728;&#x53F3;&#x8FB9;&#x6570;&#x7EC4;
        }
    }
    //&#x9012;&#x5F52;&#x6267;&#x884C;&#x4EE5;&#x4E0A;&#x64CD;&#x4F5C;&#xFF0C;&#x5BF9;&#x5DE6;&#x53F3;&#x4E24;&#x4E2A;&#x6570;&#x7EC4;&#x8FDB;&#x884C;&#x64CD;&#x4F5C;&#xFF0C;&#x76F4;&#x5230;&#x6570;&#x7EC4;&#x957F;&#x5EA6;&#x4E3A; &lt;= 1
    return quickSort1(left).concat(midIndexVal, quickSort1(right));
};
const array2 = [5, 4, 3, 2, 1];
console.log(&apos;quickSort1 &apos;, quickSort1(array2));
// quickSort1: [1, 2, 3, 4, 5]
</code></pre>
<p>&#x65B9;&#x6CD5;&#x4E8C;&#xFF1A;</p>
<pre><code class="lang-javascript">// &#x5FEB;&#x901F;&#x6392;&#x5E8F;
const quickSort = (arr, left, right) =&gt; {
    let len = arr.length,
        partitionIndex;
    left = typeof left != &apos;number&apos; ? 0 : left;
    right = typeof right != &apos;number&apos; ? len - 1 : right;

    if (left &lt; right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
};

const partition = (arr, left, right) =&gt; {
    //&#x5206;&#x533A;&#x64CD;&#x4F5C;
    let pivot = left, //&#x8BBE;&#x5B9A;&#x57FA;&#x51C6;&#x503C;&#xFF08;pivot&#xFF09;
        index = pivot + 1;
    for (let i = index; i &lt;= right; i++) {
        if (arr[i] &lt; arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
};

const swap = (arr, i, j) =&gt; {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};
</code></pre>
<p>&#x6D4B;&#x8BD5;</p>
<pre><code class="lang-javascript">// &#x6D4B;&#x8BD5;
const array = [5, 4, 3, 2, 1];
console.log(&apos;&#x539F;&#x59CB;array:&apos;, array);
const newArr = quickSort(array);
console.log(&apos;newArr:&apos;, newArr);
// &#x539F;&#x59CB; array:  [5, 4, 3, 2, 1]
// newArr:     [1, 4, 3, 2, 5]
</code></pre>
<p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li><p>&#x7B2C;&#x4E00;&#xFF0C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x56E0;&#x4E3A; partition() &#x51FD;&#x6570;&#x8FDB;&#x884C;&#x5206;&#x533A;&#x65F6;&#xFF0C;&#x4E0D;&#x9700;&#x8981;&#x5F88;&#x591A;&#x989D;&#x5916;&#x7684;&#x5185;&#x5B58;&#x7A7A;&#x95F4;&#xFF0C;&#x6240;&#x4EE5;&#x5FEB;&#x6392;&#x662F;<code>&#x539F;&#x5730;&#x6392;&#x5E8F;</code>&#x7B97;&#x6CD5;&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E8C;&#xFF0C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x548C;&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x76F8;&#x4F3C;&#xFF0C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x6BCF;&#x6B21;&#x4EA4;&#x6362;&#x7684;&#x5143;&#x7D20;&#x90FD;&#x6709;&#x53EF;&#x80FD;&#x4E0D;&#x662F;&#x76F8;&#x90BB;&#x7684;&#xFF0C;&#x56E0;&#x6B64;&#x5B83;&#x6709;&#x53EF;&#x80FD;&#x6253;&#x7834;&#x539F;&#x6765;&#x503C;&#x4E3A;&#x76F8;&#x540C;&#x7684;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x7684;&#x987A;&#x5E8F;&#x3002;&#x56E0;&#x6B64;&#xFF0C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x5E76;<code>&#x4E0D;&#x7A33;&#x5B9A;</code>&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E09;&#xFF0C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x6781;&#x7AEF;&#x7684;&#x4F8B;&#x5B50;&#xFF1A;&#x5982;&#x679C;&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x6570;&#x636E;&#x539F;&#x6765;&#x5DF2;&#x7ECF;&#x662F;&#x6709;&#x5E8F;&#x7684;&#x4E86;&#xFF0C;&#x6BD4;&#x5982; 1&#xFF0C;3&#xFF0C;5&#xFF0C;6&#xFF0C;8&#x3002;&#x5982;&#x679C;&#x6211;&#x4EEC;&#x6BCF;&#x6B21;&#x9009;&#x62E9;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x4F5C;&#x4E3A; pivot&#xFF0C;&#x90A3;&#x6BCF;&#x6B21;&#x5206;&#x533A;&#x5F97;&#x5230;&#x7684;&#x4E24;&#x4E2A;&#x533A;&#x95F4;&#x90FD;&#x662F;&#x4E0D;&#x5747;&#x7B49;&#x7684;&#x3002;&#x6211;&#x4EEC;&#x9700;&#x8981;&#x8FDB;&#x884C;&#x5927;&#x7EA6; n &#x6B21;&#x5206;&#x533A;&#x64CD;&#x4F5C;&#xFF0C;&#x624D;&#x80FD;&#x5B8C;&#x6210;&#x5FEB;&#x6392;&#x7684;&#x6574;&#x4E2A;&#x8FC7;&#x7A0B;&#x3002;&#x6BCF;&#x6B21;&#x5206;&#x533A;&#x6211;&#x4EEC;&#x5E73;&#x5747;&#x8981;&#x626B;&#x63CF;&#x5927;&#x7EA6; n / 2 &#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x8FD9;&#x79CD;&#x60C5;&#x51B5;&#x4E0B;&#xFF0C;&#x5FEB;&#x6392;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x5C31;&#x4ECE; O(nlogn) &#x9000;&#x5316;&#x6210;&#x4E86; O(n<sup>2</sup>)&#x3002;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log n)&#x3002;
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n<sup>2</sup>)&#x3002;
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log n)&#x3002;</p>
</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-708f5b687f6bde65.gif?imageMogr2/auto-orient/strip" alt="quick-sort.gif"></p>
<p><strong>&#x89E3;&#x7B54;&#x5F00;&#x7BC7;&#x95EE;&#x9898;</strong></p>
<p>&#x5FEB;&#x6392;&#x548C;&#x5F52;&#x5E76;&#x7528;&#x7684;&#x90FD;&#x662F;&#x5206;&#x6CBB;&#x601D;&#x60F3;&#xFF0C;&#x9012;&#x63A8;&#x516C;&#x5F0F;&#x548C;&#x9012;&#x5F52;&#x4EE3;&#x7801;&#x4E5F;&#x975E;&#x5E38;&#x76F8;&#x4F3C;&#xFF0C;&#x90A3;&#x5B83;&#x4EEC;&#x7684;&#x533A;&#x522B;&#x5728;&#x54EA;&#x91CC;&#x5462; &#xFF1F;</p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-3e29b9d2d936905d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x4E0E;&#x5F52;&#x5E76;&#x6392;&#x5E8F;"></p>
<p>&#x53EF;&#x4EE5;&#x53D1;&#x73B0;&#xFF1A;</p>
<ul>
<li>&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x7684;&#x5904;&#x7406;&#x8FC7;&#x7A0B;&#x662F;<code>&#x7531;&#x4E0B;&#x800C;&#x4E0A;</code>&#x7684;&#xFF0C;&#x5148;&#x5904;&#x7406;&#x5B50;&#x95EE;&#x9898;&#xFF0C;&#x7136;&#x540E;&#x518D;&#x5408;&#x5E76;&#x3002;</li>
<li>&#x800C;&#x5FEB;&#x6392;&#x6B63;&#x597D;&#x76F8;&#x53CD;&#xFF0C;&#x5B83;&#x7684;&#x5904;&#x7406;&#x8FC7;&#x7A0B;&#x662F;<code>&#x7531;&#x4E0A;&#x800C;&#x4E0B;</code>&#x7684;&#xFF0C;&#x5148;&#x5206;&#x533A;&#xFF0C;&#x7136;&#x540E;&#x518D;&#x5904;&#x7406;&#x5B50;&#x95EE;&#x9898;&#x3002;</li>
<li>&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x867D;&#x7136;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x3001;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(nlogn) &#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x4F46;&#x662F;&#x5B83;&#x662F;&#x975E;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
<li>&#x5F52;&#x5E76;&#x4E4B;&#x6240;&#x4EE5;&#x662F;&#x975E;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x4E3B;&#x8981;&#x539F;&#x56E0;&#x662F;&#x5408;&#x5E76;&#x51FD;&#x6570;&#x65E0;&#x6CD5;&#x5728;&#x539F;&#x5730;&#x6267;&#x884C;&#x3002;</li>
<li>&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x901A;&#x8FC7;&#x8BBE;&#x8BA1;&#x5DE7;&#x5999;&#x7684;&#x539F;&#x5730;&#x5206;&#x533A;&#x51FD;&#x6570;&#xFF0C;&#x53EF;&#x4EE5;&#x5B9E;&#x73B0;&#x539F;&#x5730;&#x6392;&#x5E8F;&#xFF0C;&#x89E3;&#x51B3;&#x4E86;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x5360;&#x7528;&#x592A;&#x591A;&#x5185;&#x5B58;&#x7684;&#x95EE;&#x9898;&#x3002;</li>
</ul>
<h3 id="36-&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#xFF08;shell-sort&#xFF09;"><a name="36-&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#xFF08;shell-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#36-&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#xFF08;shell-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.6 &#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#xFF08;Shell Sort&#xFF09;</h3>
<p><strong>&#x601D;&#x60F3;</strong></p>
<ul>
<li>&#x5148;&#x5C06;&#x6574;&#x4E2A;&#x5F85;&#x6392;&#x5E8F;&#x7684;&#x8BB0;&#x5F55;&#x5E8F;&#x5217;&#x5206;&#x5272;&#x6210;&#x4E3A;&#x82E5;&#x5E72;&#x5B50;&#x5E8F;&#x5217;&#x3002;</li>
<li>&#x5206;&#x522B;&#x8FDB;&#x884C;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x3002;</li>
<li>&#x5F85;&#x6574;&#x4E2A;&#x5E8F;&#x5217;&#x4E2D;&#x7684;&#x8BB0;&#x5F55;&#x57FA;&#x672C;&#x6709;&#x5E8F;&#x65F6;&#xFF0C;&#x518D;&#x5BF9;&#x5168;&#x4F53;&#x8BB0;&#x5F55;&#x8FDB;&#x884C;&#x4F9D;&#x6B21;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x3002;</li>
</ul>
<p><strong>&#x8FC7;&#x7A0B;</strong></p>
<ol>
<li>&#x4E3E;&#x4E2A;&#x6613;&#x4E8E;&#x7406;&#x89E3;&#x7684;&#x4F8B;&#x5B50;&#xFF1A;[35, 33, 42, 10, 14, 19, 27, 44]&#xFF0C;&#x6211;&#x4EEC;&#x91C7;&#x53D6;&#x95F4;&#x9694; 4&#x3002;&#x521B;&#x5EFA;&#x4E00;&#x4E2A;&#x4F4D;&#x4E8E; 4 &#x4E2A;&#x4F4D;&#x7F6E;&#x95F4;&#x9694;&#x7684;&#x6240;&#x6709;&#x503C;&#x7684;&#x865A;&#x62DF;&#x5B50;&#x5217;&#x8868;&#x3002;&#x4E0B;&#x9762;&#x8FD9;&#x4E9B;&#x503C;&#x662F; { 35, 14 }&#xFF0C;{ 33, 19 }&#xFF0C;{ 42, 27 } &#x548C; { 10, 44 }&#x3002;</li>
</ol>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-e58310e3c89561da.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="&#x6817;&#x5B50;"></p>
<ol>
<li>&#x6211;&#x4EEC;&#x6BD4;&#x8F83;&#x6BCF;&#x4E2A;&#x5B50;&#x5217;&#x8868;&#x4E2D;&#x7684;&#x503C;&#xFF0C;&#x5E76;&#x5728;&#x539F;&#x59CB;&#x6570;&#x7EC4;&#x4E2D;&#x4EA4;&#x6362;&#x5B83;&#x4EEC;&#xFF08;&#x5982;&#x679C;&#x9700;&#x8981;&#xFF09;&#x3002;&#x5B8C;&#x6210;&#x6B64;&#x6B65;&#x9AA4;&#x540E;&#xFF0C;&#x65B0;&#x6570;&#x7EC4;&#x5E94;&#x5982;&#x4E0B;&#x6240;&#x793A;&#x3002;</li>
</ol>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-4d6b2b51ca3f04bd.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="&#x6817;&#x5B50;"></p>
<ol>
<li>&#x7136;&#x540E;&#xFF0C;&#x6211;&#x4EEC;&#x91C7;&#x7528; 2 &#x7684;&#x95F4;&#x9694;&#xFF0C;&#x8FD9;&#x4E2A;&#x95F4;&#x9699;&#x4EA7;&#x751F;&#x4E24;&#x4E2A;&#x5B50;&#x5217;&#x8868;&#xFF1A;{ 14, 27, 35, 42 }&#xFF0C; { 19, 10, 33, 44 }&#x3002;</li>
</ol>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-38dcc34caa3a9d2c.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="&#x6817;&#x5B50;"></p>
<ol>
<li>&#x6211;&#x4EEC;&#x6BD4;&#x8F83;&#x5E76;&#x4EA4;&#x6362;&#x539F;&#x59CB;&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x503C;&#xFF08;&#x5982;&#x679C;&#x9700;&#x8981;&#xFF09;&#x3002;&#x5B8C;&#x6210;&#x6B64;&#x6B65;&#x9AA4;&#x540E;&#xFF0C;&#x6570;&#x7EC4;&#x53D8;&#x6210;&#xFF1A;[14, 10, 27, 19, 35, 33, 42, 44]&#xFF0C;&#x56FE;&#x5982;&#x4E0B;&#x6240;&#x793A;&#xFF0C;10 &#x4E0E; 19 &#x7684;&#x4F4D;&#x7F6E;&#x4E92;&#x6362;&#x4E00;&#x4E0B;&#x3002;</li>
</ol>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-4fdc3019a8c4ec11.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="image.png"></p>
<ol>
<li>&#x6700;&#x540E;&#xFF0C;&#x6211;&#x4EEC;&#x4F7F;&#x7528;&#x503C;&#x95F4;&#x9694; 1 &#x5BF9;&#x6570;&#x7EC4;&#x7684;&#x5176;&#x4F59;&#x90E8;&#x5206;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#xFF0C;Shell sort &#x4F7F;&#x7528;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x5BF9;&#x6570;&#x7EC4;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;</li>
</ol>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-25f5e05762daaa49.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="&#x6817;&#x5B50;"></p>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<pre><code class="lang-javascript">const shellSort = arr =&gt; {
    let len = arr.length,
        temp,
        gap = 1;
    console.time(&apos;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    while (gap &lt; len / 3) {
        //&#x52A8;&#x6001;&#x5B9A;&#x4E49;&#x95F4;&#x9694;&#x5E8F;&#x5217;
        gap = gap * 3 + 1;
    }
    for (gap; gap &gt; 0; gap = Math.floor(gap / 3)) {
        for (let i = gap; i &lt; len; i++) {
            temp = arr[i];
            let j = i - gap;
            for (; j &gt;= 0 &amp;&amp; arr[j] &gt; temp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
            console.log(&apos;arr  :&apos;, arr);
        }
    }
    console.timeEnd(&apos;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    return arr;
};
</code></pre>
<p>&#x6D4B;&#x8BD5;</p>
<pre><code class="lang-javascript">// &#x6D4B;&#x8BD5;
const array = [35, 33, 42, 10, 14, 19, 27, 44];
console.log(&apos;&#x539F;&#x59CB;array:&apos;, array);
const newArr = shellSort(array);
console.log(&apos;newArr:&apos;, newArr);
// &#x539F;&#x59CB; array:   [35, 33, 42, 10, 14, 19, 27, 44]
// arr      :   [14, 33, 42, 10, 35, 19, 27, 44]
// arr      :   [14, 19, 42, 10, 35, 33, 27, 44]
// arr      :   [14, 19, 27, 10, 35, 33, 42, 44]
// arr      :   [14, 19, 27, 10, 35, 33, 42, 44]
// arr      :   [14, 19, 27, 10, 35, 33, 42, 44]
// arr      :   [14, 19, 27, 10, 35, 33, 42, 44]
// arr      :   [10, 14, 19, 27, 35, 33, 42, 44]
// arr      :   [10, 14, 19, 27, 35, 33, 42, 44]
// arr      :   [10, 14, 19, 27, 33, 35, 42, 44]
// arr      :   [10, 14, 19, 27, 33, 35, 42, 44]
// arr      :   [10, 14, 19, 27, 33, 35, 42, 44]
// &#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x8017;&#x65F6;: 3.592041015625ms
// newArr:     [10, 14, 19, 27, 33, 35, 42, 44]
</code></pre>
<p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li><p>&#x7B2C;&#x4E00;&#xFF0C;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x8FC7;&#x7A0B;&#x4E2D;&#xFF0C;&#x53EA;&#x6D89;&#x53CA;&#x76F8;&#x90BB;&#x6570;&#x636E;&#x7684;&#x4EA4;&#x6362;&#x64CD;&#x4F5C;&#xFF0C;&#x53EA;&#x9700;&#x8981;&#x5E38;&#x91CF;&#x7EA7;&#x7684;&#x4E34;&#x65F6;&#x7A7A;&#x95F4;&#xFF0C;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(1) &#x3002;&#x6240;&#x4EE5;&#xFF0C;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x662F;<code>&#x539F;&#x5730;&#x6392;&#x5E8F;</code>&#x7B97;&#x6CD5;&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E8C;&#xFF0C;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x6211;&#x4EEC;&#x77E5;&#x9053;&#xFF0C;&#x5355;&#x6B21;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#xFF0C;&#x5B83;&#x4E0D;&#x4F1A;&#x6539;&#x53D8;&#x76F8;&#x540C;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x7684;&#x76F8;&#x5BF9;&#x987A;&#x5E8F;&#xFF0C;&#x4F46;&#x5728;&#x591A;&#x6B21;&#x4E0D;&#x540C;&#x7684;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x8FC7;&#x7A0B;&#x4E2D;&#xFF0C;&#x76F8;&#x540C;&#x7684;&#x5143;&#x7D20;&#x53EF;&#x80FD;&#x5728;&#x5404;&#x81EA;&#x7684;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x4E2D;&#x79FB;&#x52A8;&#xFF0C;&#x53EF;&#x80FD;&#x5BFC;&#x81F4;&#x76F8;&#x540C;&#x5143;&#x7D20;&#x76F8;&#x5BF9;&#x987A;&#x5E8F;&#x53D1;&#x751F;&#x53D8;&#x5316;&#x3002;
&#x56E0;&#x6B64;&#xFF0C;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;<code>&#x4E0D;&#x7A33;&#x5B9A;</code>&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E09;&#xFF0C;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log n)&#x3002;
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log<sup>2</sup> n)&#x3002;
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log<sup>2</sup> n)&#x3002;</p>
</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-cdac5dafc537a06a.gif?imageMogr2/auto-orient/strip" alt="shell-sort.gif"></p>
<h3 id="37-&#x5806;&#x6392;&#x5E8F;&#xFF08;heap-sort&#xFF09;"><a name="37-&#x5806;&#x6392;&#x5E8F;&#xFF08;heap-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#37-&#x5806;&#x6392;&#x5E8F;&#xFF08;heap-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.7 &#x5806;&#x6392;&#x5E8F;&#xFF08;Heap Sort&#xFF09;</h3>
<p><strong>&#x5806;&#x7684;&#x5B9A;&#x4E49;</strong></p>
<p>&#x5806;&#x5176;&#x5B9E;&#x662F;&#x4E00;&#x79CD;&#x7279;&#x6B8A;&#x7684;&#x6811;&#x3002;&#x53EA;&#x8981;&#x6EE1;&#x8DB3;&#x8FD9;&#x4E24;&#x70B9;&#xFF0C;&#x5B83;&#x5C31;&#x662F;&#x4E00;&#x4E2A;&#x5806;&#x3002;</p>
<ul>
<li>&#x5806;&#x662F;&#x4E00;&#x4E2A;&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;&#x3002;
&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;&#xFF1A;&#x9664;&#x4E86;&#x6700;&#x540E;&#x4E00;&#x5C42;&#xFF0C;&#x5176;&#x4ED6;&#x5C42;&#x7684;&#x8282;&#x70B9;&#x4E2A;&#x6570;&#x90FD;&#x662F;&#x6EE1;&#x7684;&#xFF0C;&#x6700;&#x540E;&#x4E00;&#x5C42;&#x7684;&#x8282;&#x70B9;&#x90FD;&#x9760;&#x5DE6;&#x6392;&#x5217;&#x3002;</li>
<li>&#x5806;&#x4E2D;&#x6BCF;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x503C;&#x90FD;&#x5FC5;&#x987B;&#x5927;&#x4E8E;&#x7B49;&#x4E8E;&#xFF08;&#x6216;&#x5C0F;&#x4E8E;&#x7B49;&#x4E8E;&#xFF09;&#x5176;&#x5B50;&#x6811;&#x4E2D;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x503C;&#x3002;
&#x4E5F;&#x53EF;&#x4EE5;&#x8BF4;&#xFF1A;&#x5806;&#x4E2D;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x503C;&#x90FD;&#x5927;&#x4E8E;&#x7B49;&#x4E8E;&#xFF08;&#x6216;&#x8005;&#x5C0F;&#x4E8E;&#x7B49;&#x4E8E;&#xFF09;&#x5176;&#x5DE6;&#x53F3;&#x5B50;&#x8282;&#x70B9;&#x7684;&#x503C;&#x3002;&#x8FD9;&#x4E24;&#x79CD;&#x8868;&#x8FF0;&#x662F;&#x7B49;&#x4EF7;&#x7684;&#x3002;</li>
</ul>
<p>&#x5BF9;&#x4E8E;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x503C;&#x90FD;<code>&#x5927;&#x4E8E;&#x7B49;&#x4E8E;</code>&#x5B50;&#x6811;&#x4E2D;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x503C;&#x7684;&#x5806;&#xFF0C;&#x6211;&#x4EEC;&#x53EB;&#x4F5C;<code>&#x5927;&#x9876;&#x5806;</code>&#x3002;
&#x5BF9;&#x4E8E;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x503C;&#x90FD;<code>&#x5C0F;&#x4E8E;&#x7B49;&#x4E8E;</code>&#x5B50;&#x6811;&#x4E2D;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x503C;&#x7684;&#x5806;&#xFF0C;&#x6211;&#x4EEC;&#x53EB;&#x4F5C;<code>&#x5C0F;&#x9876;&#x5806;</code>&#x3002;</p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-ba0004cfc2c4c8d4.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="&#x533A;&#x5206;&#x5806;&#x3001;&#x5927;&#x9876;&#x5806;&#x3001;&#x5C0F;&#x9876;&#x5806;"></p>
<p>&#x5176;&#x4E2D;&#x56FE; 1 &#x548C; &#x56FE; 2 &#x662F;&#x5927;&#x9876;&#x5806;&#xFF0C;&#x56FE; 3 &#x662F;&#x5C0F;&#x9876;&#x5806;&#xFF0C;&#x56FE; 4 &#x4E0D;&#x662F;&#x5806;&#x3002;&#x9664;&#x6B64;&#x4E4B;&#x5916;&#xFF0C;&#x4ECE;&#x56FE;&#x4E2D;&#x8FD8;&#x53EF;&#x4EE5;&#x770B;&#x51FA;&#x6765;&#xFF0C;&#x5BF9;&#x4E8E;&#x540C;&#x4E00;&#x7EC4;&#x6570;&#x636E;&#xFF0C;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x6784;&#x5EFA;&#x591A;&#x79CD;&#x4E0D;&#x540C;&#x5F62;&#x6001;&#x7684;&#x5806;&#x3002;</p>
<p><strong>&#x601D;&#x60F3;</strong></p>
<ol>
<li>&#x5C06;&#x521D;&#x59CB;&#x5F85;&#x6392;&#x5E8F;&#x5173;&#x952E;&#x5B57;&#x5E8F;&#x5217; (R1, R2 .... Rn) &#x6784;&#x5EFA;&#x6210;&#x5927;&#x9876;&#x5806;&#xFF0C;&#x6B64;&#x5806;&#x4E3A;&#x521D;&#x59CB;&#x7684;&#x65E0;&#x5E8F;&#x533A;&#xFF1B;</li>
<li>&#x5C06;&#x5806;&#x9876;&#x5143;&#x7D20; R[1] &#x4E0E;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5143;&#x7D20; R[n] &#x4EA4;&#x6362;&#xFF0C;&#x6B64;&#x65F6;&#x5F97;&#x5230;&#x65B0;&#x7684;&#x65E0;&#x5E8F;&#x533A; (R1, R2, ..... Rn-1) &#x548C;&#x65B0;&#x7684;&#x6709;&#x5E8F;&#x533A; (Rn) &#xFF0C;&#x4E14;&#x6EE1;&#x8DB3; R[1, 2 ... n-1] &lt;= R[n]&#x3002;</li>
<li>&#x7531;&#x4E8E;&#x4EA4;&#x6362;&#x540E;&#x65B0;&#x7684;&#x5806;&#x9876; R[1] &#x53EF;&#x80FD;&#x8FDD;&#x53CD;&#x5806;&#x7684;&#x6027;&#x8D28;&#xFF0C;&#x56E0;&#x6B64;&#x9700;&#x8981;&#x5BF9;&#x5F53;&#x524D;&#x65E0;&#x5E8F;&#x533A; (R1, R2 ...... Rn-1) &#x8C03;&#x6574;&#x4E3A;&#x65B0;&#x5806;&#xFF0C;&#x7136;&#x540E;&#x518D;&#x6B21;&#x5C06; R[1] &#x4E0E;&#x65E0;&#x5E8F;&#x533A;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x4EA4;&#x6362;&#xFF0C;&#x5F97;&#x5230;&#x65B0;&#x7684;&#x65E0;&#x5E8F;&#x533A; (R1, R2 .... Rn-2) &#x548C;&#x65B0;&#x7684;&#x6709;&#x5E8F;&#x533A; (Rn-1, Rn)&#x3002;&#x4E0D;&#x65AD;&#x91CD;&#x590D;&#x6B64;&#x8FC7;&#x7A0B;&#xFF0C;&#x76F4;&#x5230;&#x6709;&#x5E8F;&#x533A;&#x7684;&#x5143;&#x7D20;&#x4E2A;&#x6570;&#x4E3A; n - 1&#xFF0C;&#x5219;&#x6574;&#x4E2A;&#x6392;&#x5E8F;&#x8FC7;&#x7A0B;&#x5B8C;&#x6210;&#x3002;</li>
</ol>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<pre><code class="lang-javascript">// &#x5806;&#x6392;&#x5E8F;
const heapSort = array =&gt; {
    console.time(&apos;&#x5806;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    // &#x521D;&#x59CB;&#x5316;&#x5927;&#x9876;&#x5806;&#xFF0C;&#x4ECE;&#x7B2C;&#x4E00;&#x4E2A;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;
    for (let i = Math.floor(array.length / 2 - 1); i &gt;= 0; i--) {
        heapify(array, i, array.length);
    }
    // &#x6392;&#x5E8F;&#xFF0C;&#x6BCF;&#x4E00;&#x6B21; for &#x5FAA;&#x73AF;&#x627E;&#x51FA;&#x4E00;&#x4E2A;&#x5F53;&#x524D;&#x6700;&#x5927;&#x503C;&#xFF0C;&#x6570;&#x7EC4;&#x957F;&#x5EA6;&#x51CF;&#x4E00;
    for (let i = Math.floor(array.length - 1); i &gt; 0; i--) {
        // &#x6839;&#x8282;&#x70B9;&#x4E0E;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x4EA4;&#x6362;
        swap(array, 0, i);
        // &#x4ECE;&#x6839;&#x8282;&#x70B9;&#x5F00;&#x59CB;&#x8C03;&#x6574;&#xFF0C;&#x5E76;&#x4E14;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x5DF2;&#x7ECF;&#x4E3A;&#x5F53;&#x524D;&#x6700;&#x5927;&#x503C;&#xFF0C;&#x4E0D;&#x9700;&#x8981;&#x518D;&#x53C2;&#x4E0E;&#x6BD4;&#x8F83;&#xFF0C;&#x6240;&#x4EE5;&#x7B2C;&#x4E09;&#x4E2A;&#x53C2;&#x6570;&#x4E3A; i&#xFF0C;&#x5373;&#x6BD4;&#x8F83;&#x5230;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x524D;&#x4E00;&#x4E2A;&#x5373;&#x53EF;
        heapify(array, 0, i);
    }
    console.timeEnd(&apos;&#x5806;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    return array;
};

// &#x4EA4;&#x6362;&#x4E24;&#x4E2A;&#x8282;&#x70B9;
const swap = (array, i, j) =&gt; {
    let temp = array[i];
    array[i] = array[j];
    array[j] = temp;
};

// &#x5C06; i &#x7ED3;&#x70B9;&#x4EE5;&#x4E0B;&#x7684;&#x5806;&#x6574;&#x7406;&#x4E3A;&#x5927;&#x9876;&#x5806;&#xFF0C;&#x6CE8;&#x610F;&#x8FD9;&#x4E00;&#x6B65;&#x5B9E;&#x73B0;&#x7684;&#x57FA;&#x7840;&#x5B9E;&#x9645;&#x4E0A;&#x662F;&#xFF1A;
// &#x5047;&#x8BBE;&#x7ED3;&#x70B9; i &#x4EE5;&#x4E0B;&#x7684;&#x5B50;&#x5806;&#x5DF2;&#x7ECF;&#x662F;&#x4E00;&#x4E2A;&#x5927;&#x9876;&#x5806;&#xFF0C;heapify &#x51FD;&#x6570;&#x5B9E;&#x73B0;&#x7684;
// &#x529F;&#x80FD;&#x662F;&#x5B9E;&#x9645;&#x4E0A;&#x662F;&#xFF1A;&#x627E;&#x5230; &#x7ED3;&#x70B9; i &#x5728;&#x5305;&#x62EC;&#x7ED3;&#x70B9; i &#x7684;&#x5806;&#x4E2D;&#x7684;&#x6B63;&#x786E;&#x4F4D;&#x7F6E;&#x3002;
// &#x540E;&#x9762;&#x5C06;&#x5199;&#x4E00;&#x4E2A; for &#x5FAA;&#x73AF;&#xFF0C;&#x4ECE;&#x7B2C;&#x4E00;&#x4E2A;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#xFF0C;&#x5BF9;&#x6BCF;&#x4E00;&#x4E2A;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;
// &#x90FD;&#x6267;&#x884C; heapify &#x64CD;&#x4F5C;&#xFF0C;&#x6240;&#x4EE5;&#x5C31;&#x6EE1;&#x8DB3;&#x4E86;&#x7ED3;&#x70B9; i &#x4EE5;&#x4E0B;&#x7684;&#x5B50;&#x5806;&#x5DF2;&#x7ECF;&#x662F;&#x4E00;&#x5927;&#x9876;&#x5806;
const heapify = (array, i, length) =&gt; {
    let temp = array[i]; // &#x5F53;&#x524D;&#x7236;&#x8282;&#x70B9;
    // j &lt; length &#x7684;&#x76EE;&#x7684;&#x662F;&#x5BF9;&#x7ED3;&#x70B9; i &#x4EE5;&#x4E0B;&#x7684;&#x7ED3;&#x70B9;&#x5168;&#x90E8;&#x505A;&#x987A;&#x5E8F;&#x8C03;&#x6574;
    for (let j = 2 * i + 1; j &lt; length; j = 2 * j + 1) {
        temp = array[i]; // &#x5C06; array[i] &#x53D6;&#x51FA;&#xFF0C;&#x6574;&#x4E2A;&#x8FC7;&#x7A0B;&#x76F8;&#x5F53;&#x4E8E;&#x627E;&#x5230; array[i] &#x5E94;&#x5904;&#x4E8E;&#x7684;&#x4F4D;&#x7F6E;
        if (j + 1 &lt; length &amp;&amp; array[j] &lt; array[j + 1]) {
            j++; // &#x627E;&#x5230;&#x4E24;&#x4E2A;&#x5B69;&#x5B50;&#x4E2D;&#x8F83;&#x5927;&#x7684;&#x4E00;&#x4E2A;&#xFF0C;&#x518D;&#x4E0E;&#x7236;&#x8282;&#x70B9;&#x6BD4;&#x8F83;
        }
        if (temp &lt; array[j]) {
            swap(array, i, j); // &#x5982;&#x679C;&#x7236;&#x8282;&#x70B9;&#x5C0F;&#x4E8E;&#x5B50;&#x8282;&#x70B9;:&#x4EA4;&#x6362;&#xFF1B;&#x5426;&#x5219;&#x8DF3;&#x51FA;
            i = j; // &#x4EA4;&#x6362;&#x540E;&#xFF0C;temp &#x7684;&#x4E0B;&#x6807;&#x53D8;&#x4E3A; j
        } else {
            break;
        }
    }
};
</code></pre>
<p>&#x6D4B;&#x8BD5;</p>
<pre><code class="lang-javascript">const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log(&apos;&#x539F;&#x59CB;array:&apos;, array);
const newArr = heapSort(array);
console.log(&apos;newArr:&apos;, newArr);
// &#x539F;&#x59CB; array:  [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
// &#x5806;&#x6392;&#x5E8F;&#x8017;&#x65F6;: 0.15087890625ms
// newArr:     [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]
</code></pre>
<p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li>&#x7B2C;&#x4E00;&#xFF0C;&#x5806;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x6574;&#x4E2A;&#x5806;&#x6392;&#x5E8F;&#x7684;&#x8FC7;&#x7A0B;&#xFF0C;&#x90FD;&#x53EA;&#x9700;&#x8981;&#x6781;&#x4E2A;&#x522B;&#x4E34;&#x65F6;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;&#xFF0C;&#x6240;&#x4EE5;&#x5806;&#x6392;&#x5E8F;<code>&#x662F;</code>&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
<li><p>&#x7B2C;&#x4E8C;&#xFF0C;&#x5806;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x56E0;&#x4E3A;&#x5728;&#x6392;&#x5E8F;&#x7684;&#x8FC7;&#x7A0B;&#xFF0C;&#x5B58;&#x5728;&#x5C06;&#x5806;&#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x8DDF;&#x5806;&#x9876;&#x8282;&#x70B9;&#x4E92;&#x6362;&#x7684;&#x64CD;&#x4F5C;&#xFF0C;&#x6240;&#x4EE5;&#x5C31;&#x6709;&#x53EF;&#x80FD;&#x6539;&#x53D8;&#x503C;&#x76F8;&#x540C;&#x6570;&#x636E;&#x7684;&#x539F;&#x59CB;&#x76F8;&#x5BF9;&#x987A;&#x5E8F;&#x3002;
&#x6240;&#x4EE5;&#xFF0C;&#x5806;&#x6392;&#x5E8F;&#x662F;<code>&#x4E0D;&#x7A33;&#x5B9A;</code>&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E09;&#xFF0C;&#x5806;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x5806;&#x6392;&#x5E8F;&#x5305;&#x62EC;&#x5EFA;&#x5806;&#x548C;&#x6392;&#x5E8F;&#x4E24;&#x4E2A;&#x64CD;&#x4F5C;&#xFF0C;&#x5EFA;&#x5806;&#x8FC7;&#x7A0B;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; O(n)&#xFF0C;&#x6392;&#x5E8F;&#x8FC7;&#x7A0B;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; O(nlogn)&#xFF0C;&#x6240;&#x4EE5;&#xFF0C;&#x5806;&#x6392;&#x5E8F;&#x6574;&#x4F53;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; O(nlogn)&#x3002;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log n)&#x3002;
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log n)&#x3002;
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n log n)&#x3002;</p>
</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-62cc8c35ce449e02.gif?imageMogr2/auto-orient/strip" alt="heap-sort.gif"></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-7946ab6ef624c184.gif?imageMogr2/auto-orient/strip" alt="heap-sort2.gif"></p>
<h3 id="38-&#x6876;&#x6392;&#x5E8F;&#xFF08;bucket-sort&#xFF09;"><a name="38-&#x6876;&#x6392;&#x5E8F;&#xFF08;bucket-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#38-&#x6876;&#x6392;&#x5E8F;&#xFF08;bucket-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.8 &#x6876;&#x6392;&#x5E8F;&#xFF08;Bucket Sort&#xFF09;</h3>
<p>&#x6876;&#x6392;&#x5E8F;&#x662F;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x7684;&#x5347;&#x7EA7;&#x7248;&#xFF0C;&#x4E5F;&#x91C7;&#x7528;&#x4E86;<code>&#x5206;&#x6CBB;&#x601D;&#x60F3;</code>&#x3002;</p>
<p><strong>&#x601D;&#x60F3;</strong></p>
<ul>
<li>&#x5C06;&#x8981;&#x6392;&#x5E8F;&#x7684;&#x6570;&#x636E;&#x5206;&#x5230;&#x6709;&#x9650;&#x6570;&#x91CF;&#x7684;&#x51E0;&#x4E2A;&#x6709;&#x5E8F;&#x7684;&#x6876;&#x91CC;&#x3002;</li>
<li>&#x6BCF;&#x4E2A;&#x6876;&#x91CC;&#x7684;&#x6570;&#x636E;&#x518D;&#x5355;&#x72EC;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#xFF08;&#x4E00;&#x822C;&#x7528;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x6216;&#x8005;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#xFF09;&#x3002;</li>
<li>&#x6876;&#x5185;&#x6392;&#x5B8C;&#x5E8F;&#x4E4B;&#x540E;&#xFF0C;&#x518D;&#x628A;&#x6BCF;&#x4E2A;&#x6876;&#x91CC;&#x7684;&#x6570;&#x636E;&#x6309;&#x7167;&#x987A;&#x5E8F;&#x4F9D;&#x6B21;&#x53D6;&#x51FA;&#xFF0C;&#x7EC4;&#x6210;&#x7684;&#x5E8F;&#x5217;&#x5C31;&#x662F;&#x6709;&#x5E8F;&#x7684;&#x4E86;&#x3002;</li>
</ul>
<p>&#x6BD4;&#x5982;&#xFF1A;</p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-fbe2b3e3d6d56b8e.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt=""></p>
<p>&#x6876;&#x6392;&#x5E8F;&#x5229;&#x7528;&#x4E86;&#x51FD;&#x6570;&#x7684;&#x6620;&#x5C04;&#x5173;&#x7CFB;&#xFF0C;&#x9AD8;&#x6548;&#x4E0E;&#x5426;&#x7684;&#x5173;&#x952E;&#x5C31;&#x5728;&#x4E8E;&#x8FD9;&#x4E2A;&#x6620;&#x5C04;&#x51FD;&#x6570;&#x7684;&#x786E;&#x5B9A;&#x3002;</p>
<p>&#x4E3A;&#x4E86;&#x4F7F;&#x6876;&#x6392;&#x5E8F;&#x66F4;&#x52A0;&#x9AD8;&#x6548;&#xFF0C;&#x6211;&#x4EEC;&#x9700;&#x8981;&#x505A;&#x5230;&#x8FD9;&#x4E24;&#x70B9;&#xFF1A;</p>
<ul>
<li>&#x5728;&#x989D;&#x5916;&#x7A7A;&#x95F4;&#x5145;&#x8DB3;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#xFF0C;&#x5C3D;&#x91CF;&#x589E;&#x5927;&#x6876;&#x7684;&#x6570;&#x91CF;&#x3002;</li>
<li>&#x4F7F;&#x7528;&#x7684;&#x6620;&#x5C04;&#x51FD;&#x6570;&#x80FD;&#x591F;&#x5C06;&#x8F93;&#x5165;&#x7684; N &#x4E2A;&#x6570;&#x636E;&#x5747;&#x5300;&#x7684;&#x5206;&#x914D;&#x5230; K &#x4E2A;&#x6876;&#x4E2D;&#x3002;</li>
</ul>
<p>&#x6876;&#x6392;&#x5E8F;&#x7684;&#x6838;&#x5FC3;&#xFF1A;&#x5C31;&#x5728;&#x4E8E;&#x600E;&#x4E48;&#x628A;&#x5143;&#x7D20;&#x5E73;&#x5747;&#x5206;&#x914D;&#x5230;&#x6BCF;&#x4E2A;&#x6876;&#x91CC;&#xFF0C;&#x5408;&#x7406;&#x7684;&#x5206;&#x914D;&#x5C06;&#x5927;&#x5927;&#x63D0;&#x9AD8;&#x6392;&#x5E8F;&#x7684;&#x6548;&#x7387;&#x3002;</p>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<pre><code class="lang-javascript">// &#x6876;&#x6392;&#x5E8F;
const bucketSort = (array, bucketSize) =&gt; {
  if (array.length === 0) {
    return array;
  }

  console.time(&apos;&#x6876;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
  let i = 0;
  let minValue = array[0];
  let maxValue = array[0];
  for (i = 1; i &lt; array.length; i++) {
    if (array[i] &lt; minValue) {
      minValue = array[i]; //&#x8F93;&#x5165;&#x6570;&#x636E;&#x7684;&#x6700;&#x5C0F;&#x503C;
    } else if (array[i] &gt; maxValue) {
      maxValue = array[i]; //&#x8F93;&#x5165;&#x6570;&#x636E;&#x7684;&#x6700;&#x5927;&#x503C;
    }
  }

  //&#x6876;&#x7684;&#x521D;&#x59CB;&#x5316;
  const DEFAULT_BUCKET_SIZE = 5; //&#x8BBE;&#x7F6E;&#x6876;&#x7684;&#x9ED8;&#x8BA4;&#x6570;&#x91CF;&#x4E3A; 5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (i = 0; i &lt; buckets.length; i++) {
    buckets[i] = [];
  }

  //&#x5229;&#x7528;&#x6620;&#x5C04;&#x51FD;&#x6570;&#x5C06;&#x6570;&#x636E;&#x5206;&#x914D;&#x5230;&#x5404;&#x4E2A;&#x6876;&#x4E2D;
  for (i = 0; i &lt; array.length; i++) {
    buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]);
  }

  array.length = 0;
  for (i = 0; i &lt; buckets.length; i++) {
    quickSort(buckets[i]); //&#x5BF9;&#x6BCF;&#x4E2A;&#x6876;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#xFF0C;&#x8FD9;&#x91CC;&#x4F7F;&#x7528;&#x4E86;&#x5FEB;&#x901F;&#x6392;&#x5E8F;
    for (var j = 0; j &lt; buckets[i].length; j++) {
      array.push(buckets[i][j]);
    }
  }
  console.timeEnd(&apos;&#x6876;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);

  return array;
};

// &#x5FEB;&#x901F;&#x6392;&#x5E8F;
const quickSort = (arr, left, right) =&gt; {
    let len = arr.length,
        partitionIndex;
    left = typeof left != &apos;number&apos; ? 0 : left;
    right = typeof right != &apos;number&apos; ? len - 1 : right;

    if (left &lt; right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
};

const partition = (arr, left, right) =&gt; {
    //&#x5206;&#x533A;&#x64CD;&#x4F5C;
    let pivot = left, //&#x8BBE;&#x5B9A;&#x57FA;&#x51C6;&#x503C;&#xFF08;pivot&#xFF09;
        index = pivot + 1;
    for (let i = index; i &lt;= right; i++) {
        if (arr[i] &lt; arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
};

const swap = (arr, i, j) =&gt; {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};
</code></pre>
<p><strong>&#x6D4B;&#x8BD5;</strong></p>
<pre><code class="lang-javascript">const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log(&apos;&#x539F;&#x59CB;array:&apos;, array);
const newArr = bucketSort(array);
console.log(&apos;newArr:&apos;, newArr);
// &#x539F;&#x59CB; array:  [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
// &#x5806;&#x6392;&#x5E8F;&#x8017;&#x65F6;:   0.133056640625ms
// newArr:       [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]
</code></pre>
<p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li><p>&#x7B2C;&#x4E00;&#xFF0C;&#x6876;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x56E0;&#x4E3A;&#x6876;&#x6392;&#x5E8F;&#x7684;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;&#x4E5F;&#x5373;&#x5185;&#x5B58;&#x6D88;&#x8017;&#x4E3A; O(n)&#xFF0C;&#x6240;&#x4EE5;<code>&#x4E0D;&#x662F;</code>&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E8C;&#xFF0C;&#x6876;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x53D6;&#x51B3;&#x4E8E;&#x6BCF;&#x4E2A;&#x6876;&#x7684;&#x6392;&#x5E8F;&#x65B9;&#x5F0F;&#xFF0C;&#x6BD4;&#x5982;&#xFF1A;&#x5FEB;&#x6392;&#x5C31;&#x4E0D;&#x7A33;&#x5B9A;&#xFF0C;&#x5F52;&#x5E76;&#x5C31;&#x7A33;&#x5B9A;&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E09;&#xFF0C;&#x6876;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x56E0;&#x4E3A;&#x6876;&#x5185;&#x90E8;&#x7684;&#x6392;&#x5E8F;&#x53EF;&#x4EE5;&#x6709;&#x591A;&#x79CD;&#x65B9;&#x6CD5;&#xFF0C;&#x662F;&#x4F1A;&#x5BF9;&#x6876;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4EA7;&#x751F;&#x5F88;&#x91CD;&#x5927;&#x7684;&#x5F71;&#x54CD;&#x3002;&#x6240;&#x4EE5;&#xFF0C;&#x6876;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x53EF;&#x4EE5;&#x662F;&#x591A;&#x79CD;&#x60C5;&#x51B5;&#x7684;&#x3002;
<code>&#x603B;&#x7684;&#x6765;&#x8BF4;</code>
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;&#x5F53;&#x8F93;&#x5165;&#x7684;&#x6570;&#x636E;&#x53EF;&#x4EE5;&#x5747;&#x5300;&#x7684;&#x5206;&#x914D;&#x5230;&#x6BCF;&#x4E00;&#x4E2A;&#x6876;&#x4E2D;&#x3002;
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;&#x5F53;&#x8F93;&#x5165;&#x7684;&#x6570;&#x636E;&#x88AB;&#x5206;&#x914D;&#x5230;&#x4E86;&#x540C;&#x4E00;&#x4E2A;&#x6876;&#x4E2D;&#x3002;
&#x4EE5;&#x4E0B;&#x662F;<code>&#x6876;&#x7684;&#x5185;&#x90E8;&#x6392;&#x5E8F;</code>&#x4E3A;<code>&#x5FEB;&#x901F;&#x6392;&#x5E8F;</code>&#x7684;&#x60C5;&#x51B5;&#xFF1A;
&#x5982;&#x679C;&#x8981;&#x6392;&#x5E8F;&#x7684;&#x6570;&#x636E;&#x6709; n &#x4E2A;&#xFF0C;&#x6211;&#x4EEC;&#x628A;&#x5B83;&#x4EEC;&#x5747;&#x5300;&#x5730;&#x5212;&#x5206;&#x5230; m &#x4E2A;&#x6876;&#x5185;&#xFF0C;&#x6BCF;&#x4E2A;&#x6876;&#x91CC;&#x5C31;&#x6709; k  =n / m &#x4E2A;&#x5143;&#x7D20;&#x3002;&#x6BCF;&#x4E2A;&#x6876;&#x5185;&#x90E8;&#x4F7F;&#x7528;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(k <em> logk)&#x3002;
m &#x4E2A;&#x6876;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x5C31;&#x662F; O(m </em> k <em> logk)&#xFF0C;&#x56E0;&#x4E3A; k = n / m&#xFF0C;&#x6240;&#x4EE5;&#x6574;&#x4E2A;&#x6876;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x5C31;&#x662F; O(n</em>log(n/m))&#x3002;
&#x5F53;&#x6876;&#x7684;&#x4E2A;&#x6570; m &#x63A5;&#x8FD1;&#x6570;&#x636E;&#x4E2A;&#x6570; n &#x65F6;&#xFF0C;log(n/m) &#x5C31;&#x662F;&#x4E00;&#x4E2A;&#x975E;&#x5E38;&#x5C0F;&#x7684;&#x5E38;&#x91CF;&#xFF0C;&#x8FD9;&#x4E2A;&#x65F6;&#x5019;&#x6876;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x63A5;&#x8FD1; O(n)&#x3002;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n)&#x3002;&#x5F53;&#x8F93;&#x5165;&#x7684;&#x6570;&#x636E;&#x53EF;&#x4EE5;&#x5747;&#x5300;&#x7684;&#x5206;&#x914D;&#x5230;&#x6BCF;&#x4E00;&#x4E2A;&#x6876;&#x4E2D;&#x3002;
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(nlogn)&#x3002;&#x5F53;&#x8F93;&#x5165;&#x7684;&#x6570;&#x636E;&#x88AB;&#x5206;&#x914D;&#x5230;&#x4E86;&#x540C;&#x4E00;&#x4E2A;&#x6876;&#x4E2D;&#x3002;
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n)&#x3002;</p>
</li>
</ul>
<blockquote>
<p>&#x6876;&#x6392;&#x5E8F;&#x6700;&#x597D;&#x60C5;&#x51B5;&#x4E0B;&#x4F7F;&#x7528;&#x7EBF;&#x6027;&#x65F6;&#x95F4; O(n)&#xFF0C;&#x6876;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;&#x53D6;&#x51B3;&#x4E0E;&#x5BF9;&#x5404;&#x4E2A;&#x6876;&#x4E4B;&#x95F4;&#x6570;&#x636E;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;&#x56E0;&#x4E3A;&#x5176;&#x5B83;&#x90E8;&#x5206;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x90FD;&#x4E3A; O(n)&#x3002;
&#x5F88;&#x663E;&#x7136;&#xFF0C;&#x6876;&#x5212;&#x5206;&#x7684;&#x8D8A;&#x5C0F;&#xFF0C;&#x5404;&#x4E2A;&#x6876;&#x4E4B;&#x95F4;&#x7684;&#x6570;&#x636E;&#x8D8A;&#x5C11;&#xFF0C;&#x6392;&#x5E8F;&#x6240;&#x7528;&#x7684;&#x65F6;&#x95F4;&#x4E5F;&#x4F1A;&#x8D8A;&#x5C11;&#x3002;&#x4F46;&#x76F8;&#x5E94;&#x7684;&#x7A7A;&#x95F4;&#x6D88;&#x8017;&#x5C31;&#x4F1A;&#x589E;&#x5927;&#x3002;</p>
</blockquote>
<p><strong>&#x9002;&#x7528;&#x573A;&#x666F;</strong></p>
<ul>
<li>&#x6876;&#x6392;&#x5E8F;&#x6BD4;&#x8F83;&#x9002;&#x5408;&#x7528;&#x5728;&#x5916;&#x90E8;&#x6392;&#x5E8F;&#x4E2D;&#x3002;</li>
<li>&#x5916;&#x90E8;&#x6392;&#x5E8F;&#x5C31;&#x662F;&#x6570;&#x636E;&#x5B58;&#x50A8;&#x5728;&#x5916;&#x90E8;&#x78C1;&#x76D8;&#x4E14;&#x6570;&#x636E;&#x91CF;&#x5927;&#xFF0C;&#x4F46;&#x5185;&#x5B58;&#x6709;&#x9650;&#xFF0C;&#x65E0;&#x6CD5;&#x5C06;&#x6574;&#x4E2A;&#x6570;&#x636E;&#x5168;&#x90E8;&#x52A0;&#x8F7D;&#x5230;&#x5185;&#x5B58;&#x4E2D;&#x3002;</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-96021a791180eba0.gif?imageMogr2/auto-orient/strip" alt="bocket-sort.gif"></p>
<h3 id="39-&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#xFF08;counting-sort&#xFF09;"><a name="39-&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#xFF08;counting-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#39-&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#xFF08;counting-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.9 &#x8BA1;&#x6570;&#x6392;&#x5E8F;&#xFF08;Counting Sort&#xFF09;</h3>
<p><strong>&#x601D;&#x60F3;</strong></p>
<ul>
<li>&#x627E;&#x51FA;&#x5F85;&#x6392;&#x5E8F;&#x7684;&#x6570;&#x7EC4;&#x4E2D;&#x6700;&#x5927;&#x548C;&#x6700;&#x5C0F;&#x7684;&#x5143;&#x7D20;&#x3002;</li>
<li>&#x7EDF;&#x8BA1;&#x6570;&#x7EC4;&#x4E2D;&#x6BCF;&#x4E2A;&#x503C;&#x4E3A; i &#x7684;&#x5143;&#x7D20;&#x51FA;&#x73B0;&#x7684;&#x6B21;&#x6570;&#xFF0C;&#x5B58;&#x5165;&#x65B0;&#x6570;&#x7EC4; countArr &#x7684;&#x7B2C; i &#x9879;&#x3002;</li>
<li>&#x5BF9;&#x6240;&#x6709;&#x7684;&#x8BA1;&#x6570;&#x7D2F;&#x52A0;&#xFF08;&#x4ECE; countArr &#x4E2D;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x5F00;&#x59CB;&#xFF0C;&#x6BCF;&#x4E00;&#x9879;&#x548C;&#x524D;&#x4E00;&#x9879;&#x76F8;&#x52A0;&#xFF09;&#x3002;</li>
<li>&#x53CD;&#x5411;&#x586B;&#x5145;&#x76EE;&#x6807;&#x6570;&#x7EC4;&#xFF1A;&#x5C06;&#x6BCF;&#x4E2A;&#x5143;&#x7D20; i &#x653E;&#x5728;&#x65B0;&#x6570;&#x7EC4;&#x7684;&#x7B2C; countArr[i] &#x9879;&#xFF0C;&#x6BCF;&#x653E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x5C31;&#x5C06; countArr[i] &#x51CF;&#x53BB; 1 &#x3002;</li>
</ul>
<p>&#x5173;&#x952E;&#x5728;&#x4E8E;&#x7406;&#x89E3;&#x6700;&#x540E;&#x53CD;&#x5411;&#x586B;&#x5145;&#x65F6;&#x7684;&#x64CD;&#x4F5C;&#x3002;</p>
<p><strong>&#x4F7F;&#x7528;&#x6761;&#x4EF6;</strong></p>
<ul>
<li>&#x53EA;&#x80FD;&#x7528;&#x5728;&#x6570;&#x636E;&#x8303;&#x56F4;&#x4E0D;&#x5927;&#x7684;&#x573A;&#x666F;&#x4E2D;&#xFF0C;&#x82E5;&#x6570;&#x636E;&#x8303;&#x56F4; k &#x6BD4;&#x8981;&#x6392;&#x5E8F;&#x7684;&#x6570;&#x636E; n &#x5927;&#x5F88;&#x591A;&#xFF0C;&#x5C31;&#x4E0D;&#x9002;&#x5408;&#x7528;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x3002;</li>
<li>&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x53EA;&#x80FD;&#x7ED9;&#x975E;&#x8D1F;&#x6574;&#x6570;&#x6392;&#x5E8F;&#xFF0C;&#x5176;&#x4ED6;&#x7C7B;&#x578B;&#x9700;&#x8981;&#x5728;&#x4E0D;&#x6539;&#x53D8;&#x76F8;&#x5BF9;&#x5927;&#x5C0F;&#x60C5;&#x51B5;&#x4E0B;&#xFF0C;&#x8F6C;&#x6362;&#x4E3A;&#x975E;&#x8D1F;&#x6574;&#x6570;&#x3002;</li>
<li>&#x6BD4;&#x5982;&#x5982;&#x679C;&#x8003;&#x8BD5;&#x6210;&#x7EE9;&#x7CBE;&#x786E;&#x5230;&#x5C0F;&#x6570;&#x540E;&#x4E00;&#x4F4D;&#xFF0C;&#x5C31;&#x9700;&#x8981;&#x5C06;&#x6240;&#x6709;&#x5206;&#x6570;&#x4E58;&#x4EE5; 10&#xFF0C;&#x8F6C;&#x6362;&#x4E3A;&#x6574;&#x6570;&#x3002;</li>
</ul>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<p>&#x65B9;&#x6CD5;&#x4E00;&#xFF1A;</p>
<pre><code class="lang-javascript">const countingSort = array =&gt; {
    let len = array.length,
        result = [],
        countArr = [],
        min = (max = array[0]);
    console.time(&apos;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    for (let i = 0; i &lt; len; i++) {
        // &#x83B7;&#x53D6;&#x6700;&#x5C0F;&#xFF0C;&#x6700;&#x5927; &#x503C;
        min = min &lt;= array[i] ? min : array[i];
        max = max &gt;= array[i] ? max : array[i];
        countArr[array[i]] = countArr[array[i]] ? countArr[array[i]] + 1 : 1;
    }
    console.log(&apos;countArr :&apos;, countArr);
    // &#x4ECE;&#x6700;&#x5C0F;&#x503C; -&gt; &#x6700;&#x5927;&#x503C;,&#x5C06;&#x8BA1;&#x6570;&#x9010;&#x9879;&#x76F8;&#x52A0;
    for (let j = min; j &lt; max; j++) {
        countArr[j + 1] = (countArr[j + 1] || 0) + (countArr[j] || 0);
    }
    console.log(&apos;countArr 2:&apos;, countArr);
    // countArr &#x4E2D;,&#x4E0B;&#x6807;&#x4E3A; array &#x6570;&#x503C;&#xFF0C;&#x6570;&#x636E;&#x4E3A; array &#x6570;&#x503C;&#x51FA;&#x73B0;&#x6B21;&#x6570;&#xFF1B;&#x53CD;&#x5411;&#x586B;&#x5145;&#x6570;&#x636E;&#x8FDB;&#x5165; result &#x6570;&#x636E;
    for (let k = len - 1; k &gt;= 0; k--) {
        // result[&#x4F4D;&#x7F6E;] = array &#x6570;&#x636E;
        result[countArr[array[k]] - 1] = array[k];
        // &#x51CF;&#x5C11; countArr &#x6570;&#x7EC4;&#x4E2D;&#x4FDD;&#x5B58;&#x7684;&#x8BA1;&#x6570;
        countArr[array[k]]--;
        // console.log(&quot;array[k]:&quot;, array[k], &apos;countArr[array[k]] :&apos;, countArr[array[k]],)
        console.log(&apos;result:&apos;, result);
    }
    console.timeEnd(&apos;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    return result;
};
</code></pre>
<p>&#x6D4B;&#x8BD5;</p>
<pre><code class="lang-javascript">const array = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(&apos;&#x539F;&#x59CB; array: &apos;, array);
const newArr = countingSort(array);
console.log(&apos;newArr: &apos;, newArr);
// &#x539F;&#x59CB; array:  [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]
// &#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x8017;&#x65F6;:   5.6708984375ms
// newArr:       [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]
</code></pre>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-f2541143bcd69138.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="&#x6D4B;&#x8BD5;&#x7ED3;&#x679C;"></p>
<p>&#x65B9;&#x6CD5;&#x4E8C;&#xFF1A;</p>
<pre><code class="lang-javascript">const countingSort2 = (arr, maxValue) =&gt; {
    console.time(&apos;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    maxValue = maxValue || arr.length;
    let bucket = new Array(maxValue + 1),
        sortedIndex = 0;
    (arrLen = arr.length), (bucketLen = maxValue + 1);

    for (let i = 0; i &lt; arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (let j = 0; j &lt; bucketLen; j++) {
        while (bucket[j] &gt; 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
    console.timeEnd(&apos;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    return arr;
};
</code></pre>
<p>&#x6D4B;&#x8BD5;</p>
<pre><code class="lang-javascript">const array2 = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(&apos;&#x539F;&#x59CB; array2: &apos;, array2);
const newArr2 = countingSort2(array2, 21);
console.log(&apos;newArr2: &apos;, newArr2);
// &#x539F;&#x59CB; array:  [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]
// &#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x8017;&#x65F6;:   0.043212890625ms
// newArr:       [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]
</code></pre>
<p><strong>&#x4F8B;&#x5B50;</strong></p>
<p>&#x53EF;&#x4EE5;&#x8BA4;&#x4E3A;&#xFF0C;<strong>&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x5176;&#x5B9E;&#x662F;&#x6876;&#x6392;&#x5E8F;&#x7684;&#x4E00;&#x79CD;&#x7279;&#x6B8A;&#x60C5;&#x51B5;</strong>&#x3002;</p>
<p>&#x5F53;&#x8981;&#x6392;&#x5E8F;&#x7684; n &#x4E2A;&#x6570;&#x636E;&#xFF0C;&#x6240;&#x5904;&#x7684;&#x8303;&#x56F4;&#x5E76;&#x4E0D;&#x5927;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x6BD4;&#x5982;&#x6700;&#x5927;&#x503C;&#x662F; k&#xFF0C;&#x6211;&#x4EEC;&#x5C31;&#x53EF;&#x4EE5;&#x628A;&#x6570;&#x636E;&#x5212;&#x5206;&#x6210; k &#x4E2A;&#x6876;&#x3002;&#x6BCF;&#x4E2A;&#x6876;&#x5185;&#x7684;&#x6570;&#x636E;&#x503C;&#x90FD;&#x662F;&#x76F8;&#x540C;&#x7684;&#xFF0C;&#x7701;&#x6389;&#x4E86;&#x6876;&#x5185;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x3002;</p>
<p>&#x6211;&#x4EEC;&#x90FD;&#x7ECF;&#x5386;&#x8FC7;&#x9AD8;&#x8003;&#xFF0C;&#x9AD8;&#x8003;&#x67E5;&#x5206;&#x6570;&#x7CFB;&#x7EDF;&#x4F60;&#x8FD8;&#x8BB0;&#x5F97;&#x5417;&#xFF1F;&#x6211;&#x4EEC;&#x67E5;&#x5206;&#x6570;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x7CFB;&#x7EDF;&#x4F1A;&#x663E;&#x793A;&#x6211;&#x4EEC;&#x7684;&#x6210;&#x7EE9;&#x4EE5;&#x53CA;&#x6240;&#x5728;&#x7701;&#x7684;&#x6392;&#x540D;&#x3002;&#x5982;&#x679C;&#x4F60;&#x6240;&#x5728;&#x7684;&#x7701;&#x6709; 50 &#x4E07;&#x8003;&#x751F;&#xFF0C;&#x5982;&#x4F55;&#x901A;&#x8FC7;&#x6210;&#x7EE9;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x5F97;&#x51FA;&#x540D;&#x6B21;&#x5462;&#xFF1F;</p>
<ul>
<li>&#x8003;&#x751F;&#x7684;&#x6EE1;&#x5206;&#x662F; 900 &#x5206;&#xFF0C;&#x6700;&#x5C0F;&#x662F; 0 &#x5206;&#xFF0C;&#x8FD9;&#x4E2A;&#x6570;&#x636E;&#x7684;&#x8303;&#x56F4;&#x5F88;&#x5C0F;&#xFF0C;&#x6240;&#x4EE5;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x5206;&#x6210; 901 &#x4E2A;&#x6876;&#xFF0C;&#x5BF9;&#x5E94;&#x5206;&#x6570;&#x4ECE; 0 &#x5206;&#x5230; 900 &#x5206;&#x3002;</li>
<li>&#x6839;&#x636E;&#x8003;&#x751F;&#x7684;&#x6210;&#x7EE9;&#xFF0C;&#x6211;&#x4EEC;&#x5C06;&#x8FD9; 50 &#x4E07;&#x8003;&#x751F;&#x5212;&#x5206;&#x5230;&#x8FD9; 901 &#x4E2A;&#x6876;&#x91CC;&#x3002;&#x6876;&#x5185;&#x7684;&#x6570;&#x636E;&#x90FD;&#x662F;&#x5206;&#x6570;&#x76F8;&#x540C;&#x7684;&#x8003;&#x751F;&#xFF0C;&#x6240;&#x4EE5;&#x5E76;&#x4E0D;&#x9700;&#x8981;&#x518D;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;</li>
<li>&#x6211;&#x4EEC;&#x53EA;&#x9700;&#x8981;&#x4F9D;&#x6B21;&#x626B;&#x63CF;&#x6BCF;&#x4E2A;&#x6876;&#xFF0C;&#x5C06;&#x6876;&#x5185;&#x7684;&#x8003;&#x751F;&#x4F9D;&#x6B21;&#x8F93;&#x51FA;&#x5230;&#x4E00;&#x4E2A;&#x6570;&#x7EC4;&#x4E2D;&#xFF0C;&#x5C31;&#x5B9E;&#x73B0;&#x4E86; 50 &#x4E07;&#x8003;&#x751F;&#x7684;&#x6392;&#x5E8F;&#x3002;</li>
<li>&#x56E0;&#x4E3A;&#x53EA;&#x6D89;&#x53CA;&#x626B;&#x63CF;&#x904D;&#x5386;&#x64CD;&#x4F5C;&#xFF0C;&#x6240;&#x4EE5;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; O(n)&#x3002;</li>
</ul>
<p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li>&#x7B2C;&#x4E00;&#xFF0C;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x56E0;&#x4E3A;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x7684;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(k)&#xFF0C;k &#x6876;&#x7684;&#x4E2A;&#x6570;&#xFF0C;&#x6240;&#x4EE5;&#x4E0D;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002; </li>
<li>&#x7B2C;&#x4E8C;&#xFF0C;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x4E0D;&#x6539;&#x53D8;&#x76F8;&#x540C;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x539F;&#x672C;&#x76F8;&#x5BF9;&#x7684;&#x987A;&#x5E8F;&#xFF0C;&#x56E0;&#x6B64;&#x5B83;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</li>
<li>&#x7B2C;&#x4E09;&#xFF0C;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n + k)
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n + k)
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n + k)
k &#x662F;&#x5F85;&#x6392;&#x5E8F;&#x5217;&#x6700;&#x5927;&#x503C;&#x3002;</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-43b26f260d905c77.gif?imageMogr2/auto-orient/strip" alt="counting-sort.gif"></p>
<h3 id="310-&#x57FA;&#x6570;&#x6392;&#x5E8F;&#xFF08;radix-sort&#xFF09;"><a name="310-&#x57FA;&#x6570;&#x6392;&#x5E8F;&#xFF08;radix-sort&#xFF09;" class="anchor-navigation-ex-anchor" href="#310-&#x57FA;&#x6570;&#x6392;&#x5E8F;&#xFF08;radix-sort&#xFF09;"><i class="fa fa-link" aria-hidden="true"></i></a>3.10 &#x57FA;&#x6570;&#x6392;&#x5E8F;&#xFF08;Radix Sort&#xFF09;</h3>
<p><strong>&#x601D;&#x60F3;</strong></p>
<p>&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x662F;&#x4E00;&#x79CD;&#x975E;&#x6BD4;&#x8F83;&#x578B;&#x6574;&#x6570;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x5176;&#x539F;&#x7406;&#x662F;&#x5C06;&#x6574;&#x6570;&#x6309;&#x4F4D;&#x6570;&#x5207;&#x5272;&#x6210;&#x4E0D;&#x540C;&#x7684;&#x6570;&#x5B57;&#xFF0C;&#x7136;&#x540E;&#x6309;&#x6BCF;&#x4E2A;&#x4F4D;&#x6570;&#x5206;&#x522B;&#x6BD4;&#x8F83;&#x3002;</p>
<p><strong>&#x4F8B;&#x5B50;</strong></p>
<p>&#x5047;&#x8BBE;&#x6211;&#x4EEC;&#x6709; 10 &#x4E07;&#x4E2A;&#x624B;&#x673A;&#x53F7;&#x7801;&#xFF0C;&#x5E0C;&#x671B;&#x5C06;&#x8FD9; 10 &#x4E07;&#x4E2A;&#x624B;&#x673A;&#x53F7;&#x7801;&#x4ECE;&#x5C0F;&#x5230;&#x5927;&#x6392;&#x5E8F;&#xFF0C;&#x4F60;&#x6709;&#x4EC0;&#x4E48;&#x6BD4;&#x8F83;&#x5FEB;&#x901F;&#x7684;&#x6392;&#x5E8F;&#x65B9;&#x6CD5;&#x5462; &#xFF1F;</p>
<p>&#x8FD9;&#x4E2A;&#x95EE;&#x9898;&#x91CC;&#x6709;&#x8FD9;&#x6837;&#x7684;&#x89C4;&#x5F8B;&#xFF1A;&#x5047;&#x8BBE;&#x8981;&#x6BD4;&#x8F83;&#x4E24;&#x4E2A;&#x624B;&#x673A;&#x53F7;&#x7801; a&#xFF0C;b &#x7684;&#x5927;&#x5C0F;&#xFF0C;&#x5982;&#x679C;&#x5728;&#x524D;&#x9762;&#x51E0;&#x4F4D;&#x4E2D;&#xFF0C;a &#x624B;&#x673A;&#x53F7;&#x7801;&#x5DF2;&#x7ECF;&#x6BD4; b &#x624B;&#x673A;&#x53F7;&#x7801;&#x5927;&#x4E86;&#xFF0C;&#x90A3;&#x540E;&#x9762;&#x7684;&#x51E0;&#x4F4D;&#x5C31;&#x4E0D;&#x7528;&#x770B;&#x4E86;&#x3002;&#x6240;&#x4EE5;&#x662F;&#x57FA;&#x4E8E;<code>&#x4F4D;</code>&#x6765;&#x6BD4;&#x8F83;&#x7684;&#x3002;</p>
<p>&#x6876;&#x6392;&#x5E8F;&#x3001;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x80FD;&#x6D3E;&#x4E0A;&#x7528;&#x573A;&#x5417; &#xFF1F;&#x624B;&#x673A;&#x53F7;&#x7801;&#x6709; 11 &#x4F4D;&#xFF0C;&#x8303;&#x56F4;&#x592A;&#x5927;&#xFF0C;&#x663E;&#x7136;&#x4E0D;&#x9002;&#x5408;&#x7528;&#x8FD9;&#x4E24;&#x79CD;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;&#x9488;&#x5BF9;&#x8FD9;&#x4E2A;&#x6392;&#x5E8F;&#x95EE;&#x9898;&#xFF0C;&#x6709;&#x6CA1;&#x6709;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; O(n) &#x7684;&#x7B97;&#x6CD5;&#x5462; &#xFF1F; &#x6709;&#xFF0C;&#x5C31;&#x662F;&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x3002;</p>
<p><strong>&#x4F7F;&#x7528;&#x6761;&#x4EF6;</strong></p>
<ul>
<li>&#x8981;&#x6C42;&#x6570;&#x636E;&#x53EF;&#x4EE5;&#x5206;&#x5272;&#x72EC;&#x7ACB;&#x7684;<code>&#x4F4D;</code>&#x6765;&#x6BD4;&#x8F83;&#xFF1B;</li>
<li>&#x4F4D;&#x4E4B;&#x95F4;&#x7531;&#x9012;&#x8FDB;&#x5173;&#x7CFB;&#xFF0C;&#x5982;&#x679C; a &#x6570;&#x636E;&#x7684;&#x9AD8;&#x4F4D;&#x6BD4; b &#x6570;&#x636E;&#x5927;&#xFF0C;&#x90A3;&#x4E48;&#x5269;&#x4E0B;&#x7684;&#x5730;&#x4F4D;&#x5C31;&#x4E0D;&#x7528;&#x6BD4;&#x8F83;&#x4E86;&#xFF1B;</li>
<li>&#x6BCF;&#x4E00;&#x4F4D;&#x7684;&#x6570;&#x636E;&#x8303;&#x56F4;&#x4E0D;&#x80FD;&#x592A;&#x5927;&#xFF0C;&#x8981;&#x53EF;&#x4EE5;&#x7528;&#x7EBF;&#x6027;&#x6392;&#x5E8F;&#xFF0C;&#x5426;&#x5219;&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x65E0;&#x6CD5;&#x505A;&#x5230; O(n)&#x3002;</li>
</ul>
<p><strong>&#x65B9;&#x6848;</strong></p>
<p>&#x6309;&#x7167;&#x4F18;&#x5148;&#x4ECE;&#x9AD8;&#x4F4D;&#x6216;&#x4F4E;&#x4F4D;&#x6765;&#x6392;&#x5E8F;&#x6709;&#x4E24;&#x79CD;&#x5B9E;&#x73B0;&#x65B9;&#x6848;:</p>
<ul>
<li>MSD&#xFF1A;&#x7531;&#x9AD8;&#x4F4D;&#x4E3A;&#x57FA;&#x5E95;&#xFF0C;&#x5148;&#x6309; k1 &#x6392;&#x5E8F;&#x5206;&#x7EC4;&#xFF0C;&#x540C;&#x4E00;&#x7EC4;&#x4E2D;&#x8BB0;&#x5F55;, &#x5173;&#x952E;&#x7801; k1 &#x76F8;&#x7B49;&#xFF0C;&#x518D;&#x5BF9;&#x5404;&#x7EC4;&#x6309; k2 &#x6392;&#x5E8F;&#x5206;&#x6210;&#x5B50;&#x7EC4;, &#x4E4B;&#x540E;&#xFF0C;&#x5BF9;&#x540E;&#x9762;&#x7684;&#x5173;&#x952E;&#x7801;&#x7EE7;&#x7EED;&#x8FD9;&#x6837;&#x7684;&#x6392;&#x5E8F;&#x5206;&#x7EC4;&#xFF0C;&#x76F4;&#x5230;&#x6309;&#x6700;&#x6B21;&#x4F4D;&#x5173;&#x952E;&#x7801; kd &#x5BF9;&#x5404;&#x5B50;&#x7EC4;&#x6392;&#x5E8F;&#x540E;&#xFF0C;&#x518D;&#x5C06;&#x5404;&#x7EC4;&#x8FDE;&#x63A5;&#x8D77;&#x6765;&#xFF0C;&#x4FBF;&#x5F97;&#x5230;&#x4E00;&#x4E2A;&#x6709;&#x5E8F;&#x5E8F;&#x5217;&#x3002;MSD &#x65B9;&#x5F0F;&#x9002;&#x7528;&#x4E8E;&#x4F4D;&#x6570;&#x591A;&#x7684;&#x5E8F;&#x5217;&#x3002;</li>
<li>LSD&#xFF1A;&#x7531;&#x4F4E;&#x4F4D;&#x4E3A;&#x57FA;&#x5E95;&#xFF0C;&#x5148;&#x4ECE; kd &#x5F00;&#x59CB;&#x6392;&#x5E8F;&#xFF0C;&#x518D;&#x5BF9; kd - 1 &#x8FDB;&#x884C;&#x6392;&#x5E8F;&#xFF0C;&#x4F9D;&#x6B21;&#x91CD;&#x590D;&#xFF0C;&#x76F4;&#x5230;&#x5BF9; k1 &#x6392;&#x5E8F;&#x540E;&#x4FBF;&#x5F97;&#x5230;&#x4E00;&#x4E2A;&#x6709;&#x5E8F;&#x5E8F;&#x5217;&#x3002;LSD &#x65B9;&#x5F0F;&#x9002;&#x7528;&#x4E8E;&#x4F4D;&#x6570;&#x5C11;&#x7684;&#x5E8F;&#x5217;&#x3002;</li>
</ul>
<p><strong>&#x5B9E;&#x73B0;</strong></p>
<pre><code class="lang-javascript">/**
    * name: &#x57FA;&#x6570;&#x6392;&#x5E8F;
    * @param  array &#x5F85;&#x6392;&#x5E8F;&#x6570;&#x7EC4;
    * @param  max &#x6700;&#x5927;&#x4F4D;&#x6570;
    */
const radixSort = (array, max) =&gt; {
    console.time(&apos;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    const buckets = [];
    let unit = 10,
        base = 1;
    for (let i = 0; i &lt; max; i++, base *= 10, unit *= 10) {
        for (let j = 0; j &lt; array.length; j++) {
            let index = ~~((array[j] % unit) / base); //&#x4F9D;&#x6B21;&#x8FC7;&#x6EE4;&#x51FA;&#x4E2A;&#x4F4D;&#xFF0C;&#x5341;&#x4F4D;&#x7B49;&#x7B49;&#x6570;&#x5B57;
            if (buckets[index] == null) {
                buckets[index] = []; //&#x521D;&#x59CB;&#x5316;&#x6876;
            }
            buckets[index].push(array[j]); //&#x5F80;&#x4E0D;&#x540C;&#x6876;&#x91CC;&#x6DFB;&#x52A0;&#x6570;&#x636E;
        }
        let pos = 0,
            value;
        for (let j = 0, length = buckets.length; j &lt; length; j++) {
            if (buckets[j] != null) {
                while ((value = buckets[j].shift()) != null) {
                    array[pos++] = value; //&#x5C06;&#x4E0D;&#x540C;&#x6876;&#x91CC;&#x6570;&#x636E;&#x6328;&#x4E2A;&#x635E;&#x51FA;&#x6765;&#xFF0C;&#x4E3A;&#x4E0B;&#x4E00;&#x8F6E;&#x9AD8;&#x4F4D;&#x6392;&#x5E8F;&#x505A;&#x51C6;&#x5907;&#xFF0C;&#x7531;&#x4E8E;&#x9760;&#x8FD1;&#x6876;&#x5E95;&#x7684;&#x5143;&#x7D20;&#x6392;&#x540D;&#x9760;&#x524D;&#xFF0C;&#x56E0;&#x6B64;&#x4ECE;&#x6876;&#x5E95;&#x5148;&#x635E;
                }
            }
        }
    }
    console.timeEnd(&apos;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x8017;&#x65F6;&apos;);
    return array;
};
</code></pre>
<p>&#x6D4B;&#x8BD5;</p>
<pre><code class="lang-javascript">const array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(&apos;&#x539F;&#x59CB;array:&apos;, array);
const newArr = radixSort(array, 2);
console.log(&apos;newArr:&apos;, newArr);
// &#x539F;&#x59CB; array:  [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
// &#x5806;&#x6392;&#x5E8F;&#x8017;&#x65F6;:   0.064208984375ms
// newArr:       [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
</code></pre>
<p><strong>&#x5206;&#x6790;</strong></p>
<ul>
<li><p>&#x7B2C;&#x4E00;&#xFF0C;&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x56E0;&#x4E3A;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x7684;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A; O(n + k)&#xFF0C;&#x6240;&#x4EE5;&#x4E0D;&#x662F;&#x539F;&#x5730;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002; </p>
</li>
<li><p>&#x7B2C;&#x4E8C;&#xFF0C;&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5417; &#xFF1F;
&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x4E0D;&#x6539;&#x53D8;&#x76F8;&#x540C;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x7684;&#x76F8;&#x5BF9;&#x987A;&#x5E8F;&#xFF0C;&#x56E0;&#x6B64;&#x5B83;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
</li>
<li><p>&#x7B2C;&#x4E09;&#xFF0C;&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x591A;&#x5C11; &#xFF1F;
&#x6700;&#x4F73;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n <em> k)
&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n </em> k)
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#xFF1A;T(n) = O(n * k)
&#x5176;&#x4E2D;&#xFF0C;k &#x662F;&#x5F85;&#x6392;&#x5E8F;&#x5217;&#x6700;&#x5927;&#x503C;&#x3002;</p>
</li>
</ul>
<p><strong>&#x52A8;&#x753B;</strong></p>
<p>LSD &#x57FA;&#x6570;&#x6392;&#x5E8F;&#x52A8;&#x56FE;&#x6F14;&#x793A;&#xFF1A;</p>
<p><img src="https://upload-images.jianshu.io/upload_images/12890819-aff01ef4a1e19f74.gif?imageMogr2/auto-orient/strip" alt="radixSort.gif"></p>
<h2 id="4-&#x590D;&#x6742;&#x5EA6;&#x5BF9;&#x6BD4;"><a name="4-&#x590D;&#x6742;&#x5EA6;&#x5BF9;&#x6BD4;" class="anchor-navigation-ex-anchor" href="#4-&#x590D;&#x6742;&#x5EA6;&#x5BF9;&#x6BD4;"><i class="fa fa-link" aria-hidden="true"></i></a>4. &#x590D;&#x6742;&#x5EA6;&#x5BF9;&#x6BD4;</h2>
<p>&#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684; <strong>&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E0E;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;</strong> &#x6BD4;&#x8F83;&#x3002;</p>
<table>
<thead>
<tr>
<th style="text-align:center">&#x540D;&#x79F0;</th>
<th style="text-align:center">&#x5E73;&#x5747;</th>
<th style="text-align:center">&#x6700;&#x597D;</th>
<th style="text-align:center">&#x6700;&#x574F;</th>
<th style="text-align:center">&#x7A7A;&#x95F4;</th>
<th style="text-align:center">&#x7A33;&#x5B9A;&#x6027;</th>
<th style="text-align:center">&#x6392;&#x5E8F;&#x65B9;&#x5F0F;</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">&#x5192;&#x6CE1;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n<sup>2</sup>)</td>
<td style="text-align:center">O(n)</td>
<td style="text-align:center">O(n<sup>2</sup>)</td>
<td style="text-align:center">O(1)</td>
<td style="text-align:center">Yes</td>
<td style="text-align:center">In-place</td>
</tr>
<tr>
<td style="text-align:center">&#x63D2;&#x5165;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n<sup>2</sup>)</td>
<td style="text-align:center">O(n)</td>
<td style="text-align:center">O(n<sup>2</sup>)</td>
<td style="text-align:center">O(1)</td>
<td style="text-align:center">Yes</td>
<td style="text-align:center">In-place</td>
</tr>
<tr>
<td style="text-align:center">&#x9009;&#x62E9;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n<sup>2</sup>)</td>
<td style="text-align:center">O(n<sup>2</sup>)</td>
<td style="text-align:center">O(n<sup>2</sup>)</td>
<td style="text-align:center">O(1)</td>
<td style="text-align:center">No</td>
<td style="text-align:center">In-place</td>
</tr>
<tr>
<td style="text-align:center">&#x5F52;&#x5E76;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n log n)</td>
<td style="text-align:center">O(n log n)</td>
<td style="text-align:center">O(n log n)</td>
<td style="text-align:center">O(n)</td>
<td style="text-align:center">Yes</td>
<td style="text-align:center">Out-place</td>
</tr>
<tr>
<td style="text-align:center">&#x5FEB;&#x901F;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n log n)</td>
<td style="text-align:center">O(n log n)</td>
<td style="text-align:center">O(n<sup>2</sup>)</td>
<td style="text-align:center">O(logn)</td>
<td style="text-align:center">No</td>
<td style="text-align:center">In-place</td>
</tr>
<tr>
<td style="text-align:center">&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n log n)</td>
<td style="text-align:center">O(n log<sup>2</sup> n)</td>
<td style="text-align:center">O(n log<sup>2</sup> n)</td>
<td style="text-align:center">O(1)</td>
<td style="text-align:center">No</td>
<td style="text-align:center">In-place</td>
</tr>
<tr>
<td style="text-align:center">&#x5806;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n log n)</td>
<td style="text-align:center">O(n log n)</td>
<td style="text-align:center">O(n log n)</td>
<td style="text-align:center">O(1)</td>
<td style="text-align:center">No</td>
<td style="text-align:center">In-place</td>
</tr>
<tr>
<td style="text-align:center">&#x6876;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n + k)</td>
<td style="text-align:center">O(n + k)</td>
<td style="text-align:center">O(n<sup>2</sup>)</td>
<td style="text-align:center">O(n + k)</td>
<td style="text-align:center">Yes</td>
<td style="text-align:center">Out-place</td>
</tr>
<tr>
<td style="text-align:center">&#x8BA1;&#x6570;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n + k)</td>
<td style="text-align:center">O(n + k)</td>
<td style="text-align:center">O(n + k)</td>
<td style="text-align:center">O(k)</td>
<td style="text-align:center">Yes</td>
<td style="text-align:center">Out-place</td>
</tr>
<tr>
<td style="text-align:center">&#x57FA;&#x6570;&#x6392;&#x5E8F;</td>
<td style="text-align:center">O(n * k)</td>
<td style="text-align:center">O(n * k)</td>
<td style="text-align:center">O(n * k)</td>
<td style="text-align:center">O(n + k)</td>
<td style="text-align:center">Yes</td>
<td style="text-align:center">Out-place</td>
</tr>
</tbody>
</table>
<p>&#x540D;&#x8BCD;&#x89E3;&#x91CA;&#xFF1A; </p>
<ul>
<li>n&#xFF1A;&#x6570;&#x636E;&#x89C4;&#x6A21;&#xFF1B;</li>
<li>k&#xFF1A;&#x6876;&#x7684;&#x4E2A;&#x6570;&#xFF1B;</li>
<li>In-place: &#x5360;&#x7528;&#x5E38;&#x6570;&#x5185;&#x5B58;&#xFF0C;&#x4E0D;&#x5360;&#x7528;&#x989D;&#x5916;&#x5185;&#x5B58;&#xFF1B; </li>
<li>Out-place: &#x5360;&#x7528;&#x989D;&#x5916;&#x5185;&#x5B58;&#x3002;</li>
</ul>
<h2 id="5-&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177;"><a name="5-&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177;" class="anchor-navigation-ex-anchor" href="#5-&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177;"><i class="fa fa-link" aria-hidden="true"></i></a>5. &#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177;</h2>
<ul>
<li>&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177; <a href="https://github.com/algorithm-visualizer/algorithm-visualizer" target="_blank">algorithm-visualizer</a> 
&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177; algorithm-visualizer &#x662F;&#x4E00;&#x4E2A;&#x4EA4;&#x4E92;&#x5F0F;&#x7684;&#x5728;&#x7EBF;&#x5E73;&#x53F0;&#xFF0C;&#x53EF;&#x4EE5;&#x4ECE;&#x4EE3;&#x7801;&#x4E2D;&#x53EF;&#x89C6;&#x5316;&#x7B97;&#x6CD5;&#xFF0C;&#x8FD8;&#x53EF;&#x4EE5;&#x770B;&#x5230;&#x4EE3;&#x7801;&#x6267;&#x884C;&#x7684;&#x8FC7;&#x7A0B;&#x3002;&#x65E8;&#x5728;&#x901A;&#x8FC7;&#x4EA4;&#x4E92;&#x5F0F;&#x53EF;&#x89C6;&#x5316;&#x7684;&#x6267;&#x884C;&#x6765;&#x63ED;&#x793A;&#x7B97;&#x6CD5;&#x80CC;&#x540E;&#x7684;&#x673A;&#x5236;&#x3002;
&#x6548;&#x679C;&#x5982;&#x4E0B;&#x56FE;&#xFF1A;
<img src="https://upload-images.jianshu.io/upload_images/12890819-0af779615ee7fc27.gif?imageMogr2/auto-orient/strip" alt="&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x5DE5;&#x5177;"></li>
</ul>
<ul>
<li><p>&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x52A8;&#x753B;&#x7F51;&#x7AD9; <a href="https://visualgo.net/en" target="_blank">https://visualgo.net/en</a>
&#x6548;&#x679C;&#x5982;&#x4E0B;&#x56FE;&#xFF1A;
<img src="https://upload-images.jianshu.io/upload_images/12890819-661bf75741df7c9a.gif?imageMogr2/auto-orient/strip" alt="quick-sort.gif"></p>
</li>
<li><p>&#x7B97;&#x6CD5;&#x53EF;&#x89C6;&#x5316;&#x52A8;&#x753B;&#x7F51;&#x7AD9; <a href="https://www.ee.ryerson.ca/~courses/coe428/sorting/insertionsort.html" target="_blank">www.ee.ryerson.ca</a>
&#x6548;&#x679C;&#x5982;&#x4E0B;&#x56FE;&#xFF1A;
<img src="https://upload-images.jianshu.io/upload_images/12890819-2453edc1c19e14b8.gif?imageMogr2/auto-orient/strip" alt="insert-sort.gif"></p>
</li>
</ul>
<ul>
<li><a href="https://github.com/skidding/illustrated-algorithms" target="_blank">illustrated-algorithms</a>
&#x53D8;&#x91CF;&#x548C;&#x64CD;&#x4F5C;&#x7684;&#x53EF;&#x89C6;&#x5316;&#x8868;&#x793A;&#x589E;&#x5F3A;&#x4E86;&#x63A7;&#x5236;&#x6D41;&#x548C;&#x5B9E;&#x9645;&#x6E90;&#x4EE3;&#x7801;&#x3002;&#x60A8;&#x53EF;&#x4EE5;&#x5FEB;&#x901F;&#x524D;&#x8FDB;&#x548C;&#x540E;&#x9000;&#x6267;&#x884C;&#xFF0C;&#x4EE5;&#x5BC6;&#x5207;&#x89C2;&#x5BDF;&#x7B97;&#x6CD5;&#x7684;&#x5DE5;&#x4F5C;&#x65B9;&#x5F0F;&#x3002;
&#x6548;&#x679C;&#x5982;&#x4E0B;&#x56FE;&#xFF1A;
<img src="https://upload-images.jianshu.io/upload_images/12890819-22bd05d89a89af8c.gif?imageMogr2/auto-orient/strip" alt="binary-search.gif"></li>
</ul>
<h2 id="6-&#x7CFB;&#x5217;&#x6587;&#x7AE0;"><a name="6-&#x7CFB;&#x5217;&#x6587;&#x7AE0;" class="anchor-navigation-ex-anchor" href="#6-&#x7CFB;&#x5217;&#x6587;&#x7AE0;"><i class="fa fa-link" aria-hidden="true"></i></a>6. &#x7CFB;&#x5217;&#x6587;&#x7AE0;</h2>
<p><strong>JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E;</strong> &#x7CFB;&#x5217;&#x6587;&#x7AE0;&#xFF0C;&#x6682;&#x65F6;&#x5199;&#x4E86;&#x5982;&#x4E0B;&#x7684; 11 &#x7BC7;&#x6587;&#x7AE0;&#xFF0C;&#x540E;&#x7EED;&#x8FD8;&#x6709;&#x60F3;&#x5199;&#x7684;&#x5185;&#x5BB9;&#xFF0C;&#x518D;&#x8865;&#x5145;&#x3002;</p>
<p>&#x6240;&#x5199;&#x7684;&#x5185;&#x5BB9;&#x53EA;&#x662F;&#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x5185;&#x5BB9;&#x7684;&#x51B0;&#x5C71;&#x4E00;&#x89D2;&#xFF0C;&#x5982;&#x679C;&#x4F60;&#x8FD8;&#x60F3;&#x5B66;&#x66F4;&#x591A;&#x7684;&#x5185;&#x5BB9;&#xFF0C;&#x63A8;&#x8350;&#x5B66;&#x4E60;&#x738B;&#x4E89;&#x8001;&#x5E08;&#x7684; <a href="https://time.geekbang.org/column/intro/126" target="_blank">&#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E;</a>&#x3002;</p>
<p>&#x4ECE;&#x65F6;&#x95F4;&#x548C;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x3001;&#x57FA;&#x7840;&#x6570;&#x636E;&#x7ED3;&#x6784;&#x5230;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x6587;&#x7AE0;&#x7684;&#x5185;&#x5BB9;&#x6709;&#x4E00;&#x5B9A;&#x7684;&#x5173;&#x8054;&#x6027;&#xFF0C;&#x6240;&#x4EE5;&#x9605;&#x8BFB;&#x65F6;&#x63A8;&#x8350;&#x6309;&#x987A;&#x5E8F;&#x6765;&#x9605;&#x8BFB;&#xFF0C;&#x6548;&#x679C;&#x66F4;&#x4F73;&#x3002;</p>
<ul>
<li><a href="https://github.com/biaochenxuying/blog/issues/29" target="_blank">1. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x65F6;&#x95F4;&#x548C;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;</a></li>
<li><a href="https://github.com/biaochenxuying/blog/issues/34" target="_blank">2. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x7EBF;&#x6027;&#x8868;&#xFF08;&#x6570;&#x7EC4;&#x3001;&#x961F;&#x5217;&#x3001;&#x6808;&#x3001;&#x94FE;&#x8868;&#xFF09;</a></li>
<li><a href="https://github.com/biaochenxuying/blog/issues/30" target="_blank">3. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x5B9E;&#x73B0;&#x4E00;&#x4E2A;&#x524D;&#x7AEF;&#x8DEF;&#x7531;&#xFF0C;&#x5982;&#x4F55;&#x5B9E;&#x73B0;&#x6D4F;&#x89C8;&#x5668;&#x7684;&#x524D;&#x8FDB;&#x4E0E;&#x540E;&#x9000; &#xFF1F;</a></li>
<li><a href="https://github.com/biaochenxuying/blog/issues/35" target="_blank">4. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x6808;&#x5185;&#x5B58;&#x4E0E;&#x5806;&#x5185;&#x5B58; &#x3001;&#x6D45;&#x62F7;&#x8D1D;&#x4E0E;&#x6DF1;&#x62F7;&#x8D1D;</a></li>
<li><a href="https://github.com/biaochenxuying/blog/issues/36" target="_blank">5. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x9012;&#x5F52;</a></li>
<li><a href="https://github.com/biaochenxuying/blog/issues/37" target="_blank">6. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x975E;&#x7EBF;&#x6027;&#x8868;&#xFF08;&#x6811;&#x3001;&#x5806;&#xFF09;</a></li>
<li><a href="https://github.com/biaochenxuying/blog/issues/39" target="_blank">7. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x3001;&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x3001;&#x63D2;&#x5165;&#x6392;&#x5E8F;</a></li>
<li><a href="https://github.com/biaochenxuying/blog/issues/40" target="_blank">8. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x3001;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x3001;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x3001;&#x5806;&#x6392;&#x5E8F;</a></li>
<li><a href="https://github.com/biaochenxuying/blog/issues/41" target="_blank">9. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x3001;&#x6876;&#x6392;&#x5E8F;&#x3001;&#x57FA;&#x6570;&#x6392;&#x5E8F;</a> </li>
<li><a href="https://github.com/biaochenxuying/blog/issues/42" target="_blank">10. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x5341;&#x5927;&#x7ECF;&#x5178;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x6C47;&#x603B;</a> </li>
<li><a href="https://github.com/biaochenxuying/blog/issues/43" target="_blank">11. JavaScript &#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x4E4B;&#x7F8E; - &#x5F3A;&#x70C8;&#x63A8;&#x8350; GitHub &#x4E0A;&#x503C;&#x5F97;&#x524D;&#x7AEF;&#x5B66;&#x4E60;&#x7684;&#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0E;&#x7B97;&#x6CD5;&#x9879;&#x76EE;</a></li>
</ul>
<blockquote>
<p>&#x5982;&#x679C;&#x6709;&#x9519;&#x8BEF;&#x6216;&#x8005;&#x4E0D;&#x4E25;&#x8C28;&#x7684;&#x5730;&#x65B9;&#xFF0C;&#x8BF7;&#x52A1;&#x5FC5;&#x7ED9;&#x4E88;&#x6307;&#x6B63;&#xFF0C;&#x4EE5;&#x514D;&#x8BEF;&#x4EBA;&#x5B50;&#x5F1F;&#xFF0C;&#x5341;&#x5206;&#x611F;&#x8C22;&#x3002;</p>
</blockquote>
<h2 id="7-&#x6700;&#x540E;"><a name="7-&#x6700;&#x540E;" class="anchor-navigation-ex-anchor" href="#7-&#x6700;&#x540E;"><i class="fa fa-link" aria-hidden="true"></i></a>7. &#x6700;&#x540E;</h2>
<p>&#x6587;&#x4E2D;&#x6240;&#x6709;&#x7684;&#x4EE3;&#x7801;&#x53CA;&#x6D4B;&#x8BD5;&#x4E8B;&#x4F8B;&#x90FD;&#x5DF2;&#x7ECF;&#x653E;&#x5230;&#x6211;&#x7684; <a href="https://github.com/biaochenxuying/blog/tree/master/data-structure-and-algorithms" target="_blank">GitHub</a> &#x4E0A;&#x4E86;&#x3002;</p>
<p>&#x7B14;&#x8005;&#x4E3A;&#x4E86;&#x5199;&#x597D;&#x8FD9;&#x7CFB;&#x5217;&#x7684;&#x6587;&#x7AE0;&#xFF0C;&#x82B1;&#x8D39;&#x4E86;&#x5927;&#x91CF;&#x7684;&#x4E1A;&#x4F59;&#x65F6;&#x95F4;&#xFF0C;&#x8FB9;&#x5B66;&#x8FB9;&#x5199;&#xFF0C;&#x8FB9;&#x5199;&#x8FB9;&#x4FEE;&#x6539;&#xFF0C;&#x524D;&#x540E;&#x5386;&#x65F6;&#x5DEE;&#x4E0D;&#x591A; 2 &#x4E2A;&#x6708;&#xFF0C;&#x5165;&#x95E8;&#x7EA7;&#x7684;&#x6587;&#x7AE0;&#x603B;&#x7B97;&#x662F;&#x5199;&#x5B8C;&#x4E86;&#x3002;</p>
<p>&#x5982;&#x679C;&#x4F60;&#x89C9;&#x5F97;&#x6709;&#x7528;&#x6216;&#x8005;&#x559C;&#x6B22;&#xFF0C;&#x5C31;&#x70B9;&#x6536;&#x85CF;&#xFF0C;&#x987A;&#x4FBF;&#x70B9;&#x4E2A;&#x8D5E;&#x5427;&#xFF0C;&#x4F60;&#x7684;&#x652F;&#x6301;&#x662F;&#x6211;&#x6700;&#x5927;&#x7684;&#x9F13;&#x52B1; &#xFF01;</p>
<comment> 


<footer class="page-footer"><span class="copyright">Copyright &#xA9; biaochenxuying.cn 2019 all right reserved&#xFF0C;powered by Gitbook</span><span class="footer-modification">&#x8BE5;&#x6587;&#x4EF6;&#x4FEE;&#x8BA2;&#x65F6;&#x95F4;&#xFF1A;
2019-12-08 11:02:09
</span></footer></comment>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="js-time-space.html" class="navigation navigation-prev navigation-unique" aria-label="Previous page: 时间和空间复杂度">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"十大经典排序算法","level":"1.5.2","depth":2,"previous":{"title":"时间和空间复杂度","level":"1.5.1","depth":2,"path":"views/algorithms/js-time-space.md","ref":"./views/algorithms/js-time-space.md","articles":[]},"dir":"ltr"},"config":{"plugins":["-highlight","copy-code-button","search-pro","-search","-lunr","expandable-chapters","splitter","-sharing","github-buttons","donate","tbfed-pagefooter","baidu-tongji","anchor-navigation-ex"],"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"pluginsConfig":{"tbfed-pagefooter":{"copyright":"Copyright &copy biaochenxuying.cn 2019","modify_label":"该文件修订时间：","modify_format":"YYYY-MM-DD HH:mm:ss"},"baidu-tongji":{"url":"https://hm.baidu.com/hm.js","token":"82d755d3a2e0a4df9c27c4c5895a4a81"},"splitter":{},"search-pro":{},"donate":{"alipay":"","alipayText":"支付宝打赏","button":"打赏","title":"","wechat":"https://camo.githubusercontent.com/ee094d402f957e5d656a399b9dc50ff8c010114e/68747470733a2f2f75706c6f61642d696d616765732e6a69616e7368752e696f2f75706c6f61645f696d616765732f31323839303831392d666661623762643234643038633030642e6a7065673f696d6167654d6f6772322f6175746f2d6f7269656e742f7374726970253743696d61676556696577322f322f772f31323430","wechatText":"微信打赏"},"fontsettings":{"theme":"white","family":"sans","size":2},"anchor-navigation-ex":{"associatedWithSummary":true,"float":{"floatIcon":"fa fa-navicon","level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"mode":"float","multipleH1":true,"pageTop":{"level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"printLog":false,"showGoTop":true,"showLevel":false},"github-buttons":{"buttons":[{"user":"biaochenxuying","repo":"blog","type":"star","count":true,"size":"small"},{"user":"biaochenxuying","width":"160","type":"follow","count":true,"size":"small"}]},"copy-code-button":{},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"expandable-chapters":{}},"theme":"default","author":"biaochenxuying","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"夜尽天明的博客","language":"zh-hans","gitbook":"*","description":"大前端技术为主，读书笔记、随笔、理财为辅，做个终身学习者。"},"file":{"path":"views/algorithms/js-10algo.md","mtime":"2019-12-08T03:02:09.623Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2019-12-08T03:22:38.247Z"},"basePath":"../..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../../gitbook/gitbook.js"></script>
    <script src="../../gitbook/theme.js"></script>
    
        
        <script src="../../gitbook/gitbook-plugin-copy-code-button/toggle.js"></script>
        
    
        
        <script src="../../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../../gitbook/gitbook-plugin-github-buttons/plugin.js"></script>
        
    
        
        <script src="../../gitbook/gitbook-plugin-donate/plugin.js"></script>
        
    
        
        <script src="../../gitbook/gitbook-plugin-baidu-tongji/plugin.js"></script>
        
    
        
        <script src="../../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

